Provavelmente, o que aconteceu é que o GRUB está tentando encontrar a partição formatada, mas não consegue. Quando isso acontece (eu experimentei isso), o GRUB entra no modo de recuperação.
Se for possível inicializar a partir de um "Live CD", você deve inicializá-lo (no Ubuntu) e seguir o seguinte tutorial: link
Sim, ele diz que é para depois de instalar o Windows, mas também serve perfeitamente a esse propósito.