Comment 4 for bug 657788

I had the exact same issue on upgrading from lucid to maverick.
I restored my system by booting with the 7.10 alternate disk in rescue mode, selected my drive as root and run grub-install /dev/sda.

My initially system was 7.10 or 8.04, I don't remember. The interessting thing is: the update to maverick asked me if I want to clean the system and suggested to remove some packages, I did as suggested and watched the console window. Every time it removed a kernel package it printed the remaining entries of the grub boot menu and at the end there was always an error telling something like:
blabla error /dev/sdd
/dev/sdd is an external usb disc. I ignored the error, but now I think that might was the source of the problem.