Primeiro, para o que é discutido nos fóruns e no Launchpad, tente:
sudo grub-install /dev/sdX
sudo update-grub
sudo reboot
E há um comentário útil no fórum do Kubuntu:
Eu tenho o mesmo problema com um laptop com o Ubuntu como o único sistema operacional com um BIOS não-UEFI.
Espero que ajude.