I've just realised that I seem to have had this problem on a server using LVM a while back - I didn't have time to investigate so I just put a "vgchange -ay" into the /etc/init.d/checkfs script. This is on Ubuntu 8.04 LTS server, so it's a cross-distro issue, and the hard disks are SATA.
Presumably an earlier invocation had failed, with the result that the fsck step failed, causing boot to fail. A shame that LVM, which generally helps uptime in many cases, caused downtime here - presumably btrfs wouldn't have this issue as it doesn't require this extra 'vgchange' type step.
I really look forward to btrfs (or perhaps ZFS in-kernel) being mature enough to use, largely for the parent-block checksumming to catch various errors.
This is on a home server in an inconvenient location, where there is only voltage regulation not UPS, and the utility power is flaky - so reliable unattended reboots are really helpful.