Comment 5 for bug 447696

I had this issue with mine, resolved today.

A previous update re-installed grub-legacy yet did not update the bootloader. Thus, grub2 was still the loader, but grub-legacy was only updating /boot/grub/menu.lst

Solution for me was to follow through the grub2 installation guide on the ubuntu wiki

https://wiki.ubuntu.com/Grub2

Also, instead or removing the old grub-legacy files, move them to be safe until you are sure they are no longer needed.

mkdir ~/old-grub
sudo mv /boot/grub/menu.lst* ~/old-grub

Done