Basta um Live CD de Linux (pode ser o Ubuntu) que o problema pode ser resolvido.
Após dar boot pelo Live CD, entre no sistema e abra o terminal (console). Com o terminal aberto, digite os seguintes comandos:
sudo fdisk -l (isto é um L minúsculo)
Será exibida uma tabela de partições, verifique em qual delas está instalado o seu Linux (neste exemplo vamos usar a /dev/sda3)
fdisk -l
OK, tendo em mãos a partição em que o Linux está instalado, vamos montar esta partição em um diretório. Primeiro, vamos criar o diretório onde será montada a partição:
sudo mkdir /mnt/linux
Agora montamos a partição…
sudo mount /dev/sda3 /mnt/linux
Em seguida, vamos definir o diretório montado como a nossa nova raiz:
sudo chroot /mnt/linux
Feito isso, vamos executar o GRUB:
sudo grub
Deverá ser exibido um prompt aguardando mais comandos, vamos digitar o seguinte:
find /boot/grub/stage1
Será exibido algo como (hd0,2). Anote estes números e os utilize no comando abaixo:
root (hd0,2)
setup (hd0)
Serão exibidas algumas mensagens informando que o GRUB está sendo instalado. Após isso, digite:
quit
Pronto! Seu GRUB já deve estar funcionando! Os comandos acima deverão produzir uma saída similar a da figura abaixo:
grub reinstall