you did everything correctly.
download cheat list, enable the code you want and generate the gct for that choice.
Then in game setting enable the Ocarina setting.
That's all you need.
Did you try another cheat code? maybe "always have yoshi" has a bug?
did you try with another game to see if the issue is using cheats, or it's your game?
Your game could be corrupted (the game have an antipiracy check, which is auto-patched by the loader. But maybe you are using an ISO found on some random website which is badly pre-patched?)
or you are using (or converted from) WBFS partition format, which is corrupting games just by using it.
Try dumping your game again.