To extend his comment: There is a bug in e2fsck for filesystems with many hardlinks. It could take *weeks* or longer, if it finishes at all, to run on a large filesystem with lots of hardlinks.
http://www.mail-archive.com/scientific-linux-users@listserv.fnal.gov/msg0218...
Awesome. This happens to be our exact situation - this partition is used for BackupPC which heavily relies on hard links.