Comment 2 for bug 485563

This sounds like the issue mentioned here (and probably in other places):
http://developer.amazonwebservices.com/connect/thread.jspa?threadID=24402

It appears to be some sort of negative interaction between EC2, EBS, and the xfs filesystem. I have been seeing it about 25% of the time bringing up Mercury 32-bit 0.81 with an xfs-based EBS volume (using scripts of my own crafting). It is also not limited to occurring on boot; it will happen sometimes after mounting the xfs volume manually.

I switched our instance to using ext3 and the problem went away. A shame, since I'd really prefer to use xfs, but what can you do..

Oddly, I haven't experienced this on some of our other production instances running a different AMI with a slightly different kernel. But that may just be luck..