I think arguably, both options are correct.

It is probably valid for a game publisher to claim copyright on the game's music--assuming they created it for the game [as opposed to licensing it].

I also believe that a playthrough video probably counts as fair use in most cases.

Nintendo is known for having a 'bad' reputation with playthrough videos on YouTube.