The link to Fedora's rescue mode is outdated because you type "linux rescue" nowhere.
I bet mine was a common problem: it turns out that there was not enough space for grub2 to put its files. What was needed was to shrink my boot partition by just a MB. Apparently, the first partition cannot start on sector 63 anymore with grub2.
Now, the rescue mode doesn't seem to help here, because parted doesn't offer the "resize" option. So what I needed to do was make a gparted live cd, http://sourceforge.net/projects/gpar...d-live-stable/
, then boot with that. Then move or resize the boot partition (or wherever you put grub). Once that is done, grub needs to be reconfigured and installed. In my case this meant (could have used the rescue cd as well)
mount /dev/sda2 /mnt/sysimage
mount /dev/sda1 /mnt/sysimage/boot
mount --bind /dev /mnt/sysimage/dev
mount --bind /proc /mnt/sysimage/proc
mount --bind /sys /mnt/sysimage/sys
grub2-mkconfig -o /boot/grub2/grub.cfg