What is Fedora like?

[Void Main]

Just as an FYI, did you know you could boot to any runlevel by appending the runlevel to the kernel boot line at the GRUB boot menu? That means you wouldn't have to boot into rescue mode, just press the "a" key at the GRUB menu and add a " 3" to the end of the line for runlevel 3, or 1 for single user mode (of course you can use the word "single" instead of "1" for single user mode).

As far as your actual, problem. If he's right and your partition didn't get labeled, or you have a hit or miss problem that I run into all the time on a kernel upgrade of it not recognizing the "root=LABEL=/" boot partition syntax. In this case I always replace the "root=LABLE=/" with "root=/dev/hda1" (or whatever partition your root file system resides on). If you run multi boot other Linux systems you can also run into this using the label syntax (well, you at least have to make sure your labels are unique).