Booting Ubuntu Failure : error: attempt to read or write outside of disk 'hd0'

I have spent days messing with this and researching an answer, and I was unable to find one until today. I wanted to post the solution here because I find it unlikely that I am the only one (this question has a lot of views).

The answer for me was found here: http://www.linuxquestions.org/questions/linux-laptop-and-netbook-25/boot-problem-after-installing-ubuntu-11-04-kernel-panic-not-syncing-vfs-919143/

Booting from a LiveCD and altering grub.cfg to access the block device by name instead of UUID was the fix for me. This was temporary... in that after I updated my packages, it installed a grub update that broke it. I have been messing with the grub.cfg to try and re-fix it, now, but its progress! Hope someone can fill in the next step.

Sorry for the late answer, but I recently had the very same problem. I fixed it and am posting this in the hope that it may be useful to others who experience the same problem.

In my particular case it was due to a defective SATA cable. Replacing the cable fixed the problem.

More generally—by looking at the other answer and comments—I think this message may be caused by some kind of (hardware) problem when Grub is accessing the hard drive. In sorak's case, where modifying the grub.cfg file to refer to the block device by name instead of by UUID helped, it might have been the case that for some reason, the UUID could not be read anymore.

Anyway, for whoever experiences this problem, I recommend booting a live CD and using S.M.A.R.T. tools to check whether there is a problem with the hard drive, and what kind of problem. That is is what I did; this particular answer got me started. In order to interpret the S.M.A.R.T. attributes output by smartctl for a hard drive, the Wikipedia article on S.M.A.R.T. is quite useful. For me, a high UDMA CRC Error Count hinted to a defective SATA cable, and the cable indeed turned out to be the root cause of the problem.