En la guía ubuntu salen las alternativas para recuperarlo.. la más fácil es con ese super grub no se que.. pero yo lo hago con cualquier CD de Linux, eso sí, hay que montar las particiones, hacer chroot, y reinstalar con grub-install --no-floppy /dev/sdx
Tal vez te sirve:
http://www.guia-ubuntu.org/index.php?title=Recuperar_GRUB