I am having the same problem on a Toshiba L510-016, running Fedora 12 (updated from 11) x86_64. I don't think the problem occurred until I updated from the DVD installation of Fedora 12, but it is intermittent so I can't be certain. It is definitely real, though, and extremely frustrating. It occurs in the first second after grub hands over to linux.
Edit: I should have made this clearer. The installation of Fedora 12 from the DVD as an upgrade to an existing Fedora 11 system proceeded without any problem. It was only after the upgrade, and possibly only after a yum update to the current state from the one that came on the DVD that I have this problem when I boot. The problem is intermittent although it happens on more than half the boot attempts, and never occurred with Fedora 11, which I kept updated regularly. I have no idea why it is intermittent, but if I keep trying I can get the system up eventually. Timing?, a race situation?