/etc/fstabに書かれたデバイス名が異なる時に発生するようです。
そんな時は、デバイス名をUUIDで指定すれば解決するそうです。
USBデバイスなどは、起動(認識)タイミングでデバイス名が異なる可能性がある*1ため、/etc/fstabに/dev/sdXで指定すると、fsckに失敗する場合があるみたいです。
UUIDとはUniversally Unique Identifierの略でファイルシステムの一つ一つに独自のIDを与えIDの衝突がおこらないようになっており、LinuxのファイルシステムはすべてUUIDをサポートしています。
(UUIDの調べ方)
$ sudo vol_id --export /dev/hdX | grep ID_FS_UUID
もしくは、
$ ls -l /dev/disk/by-uuid
/etc/fstabはこんな感じ。
### /etc/fstab UUID=XXYYZZXX-xxxx-yyyy-zzzz-XXXXYYYYZZZZ /home ext3 defaults 0 2
そもそもfsckをしないという選択肢もありますが。。。
*1:/dev/sdXのXの部分