pues mira por lo menos a mi cuando me ha pasado esto resulta lo siguiente , me consigo un cd de instalacion de linux y reinicio la maquina con el cd , la mayoria cuando lo reinicias con el cd adentro te preguntan que que deseas hacer y en ese momento elegis la opcion rescue.
Luego tiene que ser diferente con cada cd de recuperacion pero te voy a contar como me fue a mi cuando restaure un grub con un fedora core 2 hace algun tiempo.
Reinicie con el cd 1 de fedora core 2
puse rescue-linux (que era la opcion que activaba el rescue)
luego fedora core2 se pone a buscar una instalacion de linux , en el caso que yo lo hice estaba en un disco duro que se encontraba como master en el primer ide de la mobo, entonces me dijo que iba a cargar mi linux en la seccion /mnt/sys.rescue/ , luego venis y pones esa carpeta como tu raiz por medio de chroot /mnt/sys.rescue/
Una vez estas con la raiz pones el comando grub-install /dev/hda , lo cual instalara el grup en el disco duro primario.
recorda que depende de adonde este ubicado tu disco de arranque (disco-duro) asi es el comando puede ser
/dev/hda
/dev/hdb
/dev/hdc
/dev/hdd
todo depende de adonde este conectado tu disco duro. Y eso es todo , aproximadamente en unos 5 minutos ya tenes de nuevo grub corriendo.
Si no he sido muy claro te ruego me digas en que me falta mas explicacion :P
