You might have an actual hardware issue - HFS+ seems to be a bit fragile, and Apple's fsck_hfs (which is used by DiskUtility) isn't very god at repairing certain kinds of damage to the HFS+ file system structure.
Most of the filesystem may be fine, and the disc
may be fine - you could try DiskWarrior if you have access to a copy - you may find, though, that that will refuse to repair the disc, merely allowing you access to the contents to copy them, and, as you can do that anyway, if you have another disc which is big enough, just use Disk Utility or SuperDuper to back the disc up onto another, then wipe it recreate it from the backup. The disc may be physically faulty, in which case head crashes, dead sectors etc should have been logged by the disc's internal checking firmware (S.M.A.R.T.), so you'll want to check the S.M.A.R.T. status of the disc before committing valuable data to it. Various utilities will do this, though DiskUtility gives you a one-word summary - "SMART: Verified" if the disc seems OK.
I say "may" be fine up there because I've noticed that, when incautiously mounting journaled HFS+ volumes under Linux, the HFS+ partition gets corrupted in a way which manages to convince Disk Utility
and DiskWarrior that there are underlying hardware faults, and the only fix seems to be a reformat. Not it may be coincidence, that I've had intermittent hardware faults which happen to correspond with this kind of software corruption and go away between times, but I'm not a great believer in coincidences.
The way to avoid it, for dual-booters, by the way, is make
sure your HFS+ volumes have journaling switched off before mounting under Linux. Or just don't mount them under Linux. Or both. The
catch, which has bitten me a couple of times now, is that updates to OS X invariably (and quietly) turn journaling back on. (Thanks, Apple.) The way to avoid Apple's OS X updates catching you out like that is, probably, a very short rc.local and rc.shutdown.local script in your /etc directory which use the command line diskutil to turn journaling off at shutdown and back on at boot-up. This won't help for external drives you sometimes plug into a Linux machine - those you'll just have to leave un-journaled or remember to disable journaling on before mounting under Linux - remember, once the linux-vs-HFS+journal corruption has happened, Disk Utility and other tools seem powerless to retrieve the situation - you should be able to recover most of the data, but you'll almost certainly have to reformat the disc.
Personally, given the time and hassle of copying large chunks of data around, and the cheapness of discs these days, I'd use it as an excuse to install a bigger disc, retrieve what you need via SuperDuper or Disk Utility or whatever, then reformat the drive and keep it as a spare external.
Hope this helps someone, probably a bit late for the original poster!
