Eu tive um problema semelhante há algum tempo. Este site mostrará como montar sua instalação a partir de um CD ao vivo. No entanto, envolve muito trabalho de terminal:
Como reparar / restaurar / reinstalar o Grub 2 com um Ubuntu CD ao vivoApenas um pensamento: não siga todas as instruções, eles dizem como remover e reinstalar o grub. Se você quiser apenas atualizá-lo, siga apenas até usar o comando chroot e, em seguida, execute update-grub. Certifique-se também de usar a partição correta.
Espero que ajude.