Você precisa reinstalar o GRUB na partição do Ubuntu. Pegue um LiveCD do Ubuntu e inicialize nele.
Um você faz isso, abra o GParted. Usaremos isso para descobrir a letra do seu disco rígido e o número da sua partição do Ubuntu.
Agora, a parte sublinhada na parte superior é o dispositivo que estamos vendo (meu disco rígido), onde a parte sublinhada dentro da tabela é minha partição do Ubuntu (não estará exatamente no mesmo local da partição, procure para uma partição ext4 (ou ext3 para versões do Ubuntu anteriores a 10.04)). Precisamos desses dois quando entramos no terminal.
Em seguida, abra o Terminal up e digite o seguinte, substitua X pela letra do disco rígido e Y pelo número da partição (esses dois são mostrados dentro do GParted)
sudo mount /dev/sdXY /mnt
sudo grub-install --root-directory=/mnt /dev/sdX
Então, para o meu exemplo, eu substituiria X por um e Y por 4. (isso varia dependendo de como suas partições são configuradas, então não use essas, a menos que o GParted diga que é onde partições estão em)
Deixe funcionar e, depois que terminar, o GRUB deverá aparecer quando você inicializar o computador.