I have a dual boot system, with Mac OS X and Ubuntu running. I had read somewhere that you need to turn off journaling on Mac's HFS+ filesystem to use it from Linux, so I had religiously done that. Yesterday, I used something from my Mac volume in Linux, hadn't done any writes. Today, when I booted OS X, it just refused to go beyond the initial grey boot time screen. I gave it 20 minutes, then I shut if off. I tried it again, gave it 1hr 30min, my patience called off, and I again shut it off. If something was taking so much time at boot, I was pretty sure there was some pain in the filesystem, and turning journaling off was causing hopelessly long recovery times. But I hadn't expected to wait this long! It was getting ridiculous.
Then, I booted Linux, looked for a possible fix. Found a feasible solution, on Ubuntu forums, it was a bit broken so reproducing it here with fixes. Run the following script as su to fix inconsistent hfs+ volumes. You need build tools and libssl-dev to use this, I had to learn it the hard way.
tar zxf diskdev_cmds-332.14.tar.gz
bunzip2 -c diskdev_cmds-332.14.patch.bz2 | patch -p0
make -f Makefile.lnx
cp fsck_hfs.tproj/fsck_hfs /sbin/fsck.hfsplus
ln -s mkfs.hfsplus mkfs.hfs
ln -s fsck.hfsplus fsck.hfsn -s fsck.hfsplus fsck.hfs
Then do a "fsck.hfsplus /dev/your_mac_vol". It will take some time, depending upon how much of the fs is screwed, but much much lesser than OS X's boot time fsck. My volume was repaired in around 10 minutes. Reboot, and your shiny OS X should run like a happy kid after a nap.
I simply can't believe that OS X is incapable of fixing its own stuff. If you read the FAT fs code in Linux kernel, somewhere on the top there are two interesting words "fscking l'users", they need to be replicated somewhere.