Comment 75 for bug 441941

Try BURG from my ppa repository, first add these lines to /etc/apt/sources.list:
deb http://ppa.launchpad.net/bean123ch/burg/ubuntu karmic main
deb-src http://ppa.launchpad.net/bean123ch/burg/ubuntu karmic main

Then install with:
sudo apt-get update
sudo apt-get install grub-pc

Then, use the --safe option when installing to mbr, for example:

sudo grub-install --safe /dev/sda

This should solve the issue.