Provavelmente você instalou o GRUB no local errado.
Você precisa ter o código de inicialização do GRUB no MBR, que você deve ter, já que ele é carregado. Mas isso precisa apontar para uma partição válida contendo o restante do código do GRUB, incluindo o menu. Ou está apontando para o lugar errado ou algo mudou.
Ele pode ser corrigido facilmente, com o Super Grub Disk, o Boot Repair Disk ou o Ubuntu CD ao vivo.
Tenho certeza que você pode encontrar vários tutoriais, muitos deles em askubuntu.com.