Para recuperar el grub yo lo hago siempre mediante un livecd. Una vez que has iniciado sesion con el sólo tienes que montar la partición en la que tienes instalado linux, hacer un chroot a esa partición has montado y ejecutar grub-install sobre el disco en el que tuvieras grub.
Salu2!