@arminus: I believe having only 11 games installed might be your problem. I read somewhere you will have problems if you have less than 30 games total installed.
OK, so I found a solution to my StarTropics problem. I kept trying different versions of the game until I found one that worked. Strangely enough, the only version that works is the one where the village chief refers to the Yo-Yo as a "Star" (this was changed in the Virtual Console release, and I'm assuming the same version is used in the NES Classic Edition). So there you have it, no patch needed, you just have to find the correct version of the game.