Inicialize no Ubuntu Live CD e execute alguns comandos.
Primeiro, identifique qual é a partição do Ubuntu:
sudo fdisk -l
Em seguida, monte-o (substituindo sda2 pelo número de partição apropriado):
sudo mount /dev/sda2 /mnt
E, finalmente, reinstale o Grub (substituindo o sda pelo disco rígido apropriado):
sudo grub-install --root-directory=/mnt /dev/sda
Agora, execute isto:
sudo update-grub
Isto deve detectar sua instalação do Ubuntu e adicioná-la ao menu do Grub.