Para recuperar el grub vamos a usar un LiveCD. Te recomiendo Ubuntu por ser el más utilizado. Sólo nos interesa el gestor de arranque.
Introducimos el CD en el PC y iniciamos desde CD-ROM.
Hacemos un directorio para montar nuestra partición con Linux:
~# mkdir /mnt/ubuntu /* puedes hacer el directorio que te dé la gana, mientras te acuerdes.
Montamos la partición con una orden de montaje convencional. El formato más habitual es
ext3 y debéis localizar la partición en la que tenéis instalada Ubuntu (normalmente será algo como /dev/hda5, pero puede variar de un caso a otro).
~# mount -t ext2 partición_ubuntu /mnt/ubuntu
Ahora vamos a cambiar el origen de root de nuestro sistema de archivos al directorio en el que hemos montado Ubuntu, para que al instalar grub interprete que el "/" del sistema está ahí. Para ello usamos chroot.
~# chroot /mnt/ubuntu/
Instalamos GRUB en el MBR del primer disco duro, que normalmente estará configurado como Primary Master (hda).
~# grub-install /dev/hda
Verificamos que todo está bien revisando las entradas que se han incluído en /boot/grub/menu.lst y si están todos nuestros sistemas (que será lo más normal) ya podemos reiniciar nuestro sistema, retirar el LiveCD y disfrutar de nuestro gestor de arranque.
Creo que con eso se te arreglará.