From http://ubuntuforums.org/showthread.php?t=1285098:

Press E at the GRUB menu. Find the line saying save_env recordfail and delete all of it with the Del or Backspace key. Press Ctrl+X to boot, and then open the Terminal by searching it in the dash(launcher menu).

Run the following command, and then when it asks for your password, type it, and press Enter. Your password will not be shown, not even asterisks.

sudo -i

Then, run each command, one-by-one.

cd /boot/grub

rm grubenv

grub-editenv grubenv create

grub-editenv grubenv set default=0

grub-editenv grubenv list

update-grub

The second-to-last command should show default=0. If it does, run the last command, and let it finish. When it finishes, you should get the prompt /boot/grub# or something like that again(it's what you see after each command). Run exit twice, and then reboot.