Comment 34 for bug 391044

Doing
  sudo grub-install /dev/sda
made the problem go away for me. Since I don't really care where
grub is installed, I don't care that this presumably changes that,
I'm just glad my system boots now. (Now if only the keyboard
worked every time... but that's a different Karmic bug.)