Had similar problem as you, only difference is in number of 2nd Invalid volume header. This started with problems with encrypted backup drive which was down to corrupt file and necesitated erase and full backup. I now however get the Error message you reported but when attempting to verify my Mac HD. I haven't a clue what this means & wondered if you had learnt anything more?
Restarted in Lion Recovery Partition [Restart + Command-R]. Ran Disk Urtilities Verify & no problems reported with Mac HD. Same lack of problems with Mac HD on restarting in main partition. Threads going back to at least 10.4 reporting similar problems. General consensus appears to be that Disk Utility Verify can throw up spurious error reports (we all hope)