Yoshi, creo recordar, no aparece por arte de magia en las fases, primero tenías que descubrirlo, liberarlo, encontrarlo o lo que sea de un sitio, y así es cómo a partir de ese momento verás en todas las fases un huevo de Yoshi escondido por algún lado.
Sigue jugando las demás fases y consiguiendo Shines, no te agobies por conseguir a Yoshi ahora, seguramente si te dedicas a ir en busca de más Shines en otras fases desbloquearás a Yoshi tarde o temprano.
Suerte.