Na versão 9.10 do Ubuntu que instalei foi feita uma atualização do GRUB e todo o processo que coloquei abaixo não funciona bem, então segue o mesmo roteiro para a nova versão:

Recuperar Grub 2 com LiveCD

• De um boot com o último LiveCD do Ubuntu.
• Abra um terminal e digite

$ sudo fdisk -l

• Descubra qual a partição que o Linux está instalado, usarei "/dev/sda1" que deve ser substituído para cada caso. Definida a partição, será necessário então montá-la em /mnt :

$ sudo mount /dev/sda1 /mnt

• Em caso de ter /boot em uma área do disco separada, será necessário montála também. Neste exemplo será utilizada a partição "/dev/sda2".

$ sudo mount /dev/sda2 /mnt/boot 

OBS.: Prestar atenção para não trocar os pontos de montagem.

• Agora com o comando abaixo serão montados as outras partições.

$ sudo mount --bind /dev /mnt/dev

• Usar o comando chroot para o ponto de montagem raiz

$ sudo chroot /mnt

 

Para o comando acima é necessário que se tenha acesso de administrador no sistema, com o chroot será possível rodar comando como root sem a necessidade de utilizar o comando "sudo".

• Será necessário editar o arquivo "/etc/default/grub" para seu sistema

$ gedit /etc/default/grub

• Depois de alterado o arquivo, e salvo, será necessário executar o comanto  update-grub para criar o arquivo de configuração.

$ update-grub

• Rodando o comando grub-install /dev/sda,  será instalado o GRUB 2 na MBR:

$ grub-install /dev/sda

• Caso ocorra qualquer erro, tente rodar novamento o comando com o parâmetro "--recheck"

$ grub-install --recheck /dev/sda

• Para finalizar o chroot utilize Ctrl+D.
• Retornando para a console inicial, desfaça todos os pontos de montagem, iniciando pelo /dev

$ sudo umount /mnt/dev

• Depois a raiz do sistema ("/"). (Caso exista "/boot" em separado, esta deve ser desconectada primeiramente, pois se não fizer isso receberá a mensagem de erro informando "device busy".)

$ sudo umount /mnt

• Finalmente o sistema pode ser reiniciado.

Se existirem opções de sistemas operacionais diferentes, o comando "update-grub" pode informa que não pode encontrar a lista de partições ("Cannot find list of partitions!"). Isto deve ser ignorado - quando conseguir dar boot na instalação Linux, será preciso executar novamente update-grub e  grub-install /dev/sda como root.

Fonte: https://wiki.ubuntu.com/Grub2

########

Vou colocar por aqui algumas referências que colecionei sobre configuração do Ubuntu... quem sabe te ajuda um pouquinho.

Recuperando o Grub do Ubuntu

Sempre faço a instalação do micro colocando o Windows e depois o Linux, entretanto por vezes tenho problema no Windows e preciso reinstalá-lo, com isso o grub fica perdido. Segue um pequeno roteiro para recuperar o Linux já instalado. No meu caso uso o Ubuntu, mas acredito que em outras distribuições também funcionarão.

Inicialize algum LiveCD ( como disse acima, no meu caso o Ubuntu).
Verifique as partições do(s) seu(s) disco(s) rígido(s), digitando o seguinte comando no terminal:

$ sudo fdisk -l

A partir da listagem que irá aparece, localize a partição onde o Linux está instalado e digite o comando: (vou utilizar sda1 como exemplo, substitua nos comandos abaixo por sua referência)

Monte a particão do linux com o comando:  
$ sudo mount /dev/sda1 /mnt

Para recuperar o GRUB, digite o seguinte comando:

$ sudo grub-install --root-directory=/mnt /dev/sda1

Lembrando de substituir "/dev/sda1" pela partição raiz.

Reinicie o seu computador.