As said, with any luck running Disk Utility from the restore disc (or, if you've upgraded the OS, the OS install disc) will repair the problem and you'll be good to go.
If it still can't fix it, however (you'd see a message something like "Underlying task reported failure", and trying again gives the same message), it's possible that it will lead to corruption down the line at some later date; I've seen this happen at least a couple of times. It MIGHT be fine, but were it my hard drive I wouldn't risk it.
In this unfortunate case, an archive and install actually won't help at all, because the problem is with the format of the disk itself, not the OS. What you'd need to do is get an external hard drive, clone the internal drive to it, reformat the internal, and clone everything back over. You could do a fresh install and reimport your apps and users from the backup disk, but it's probably not necessary--just a clone/reformat/reclone would resolve the corruption.
It's also possible that a 3rd party utility (like Disk Warrior or TechToolPro) could succeed where Disk Utility fails, but if you don't already own one it'd be expensive to find out.
I reiterate, though, if Disk Utility CAN fix it, there's no need to do any of that, and you can continue on your merry way.