A while back my grub install started throwing up an invalid environment block error. It took me a while to find the fix, so I figured that someone else might want it.

To boot into linux in the first place, push e in the grub menu, delete the save_env recordfail line, and press ctrl+x to boot.

Next, run these commands:

cd /boot/grub
rm grubenv
grub-editenv grubenv create
grub-editenv grubenv set default=0
grub-editenv grubenv list
default=0

This should give you a bootable system. Found the solution here: https://bugs.launchpad.net/ubuntu/+s...b2/+bug/439784. Hope this helps someone!