str_replace the_title(); blues

That’s because the_title() echoes the title. Use this instead:

echo str_replace( 'Tutorial: ', '', get_the_title() );