Comment 22 for bug 447696

I've also been fighting the same problems for the last 6-12 months. I believe my issue was caused by having installed grub2 earlier then most everyone else. I took your advice uninstalled grub and grub2 completely with apt-get re-installed and ran the upgrade instructions from https://wiki.ubuntu.com/Grub2 and everything is working great. Hopefully there are not too many others who are stuck this way.