Espere! Não reformate ainda ...
O que provavelmente aconteceu é que o Windows não pode ver as partições ext4. Inicialize com o seu live CD do Ubuntu e use o Gparted. Deve ver as partições. Use-o para consertar o Grub.
Deixe-me saber se funciona. Eu estou escrevendo como um bat-out-of-hell para te impedir de formatar!