Repair Disk problem

So when I try to verify my disk, of late it comes with an error (similar to this):

Code:

Verifying volume “Mac HD”
Checking file systemPerforming live verification.
Checking Journaled HFS Plus volume.
Checking extents overflow file.
Checking catalog file.
Checking multi-linked files.
Checking catalog hierarchy.
Checking extended attributes file.
Checking volume bitmap.
Checking volume information.
Invalid volume file count
(It should be 398033 instead of 398018)
Invalid volume directory count
(It should be 105683 instead of 105674)
Invalid volume free block count
(It should be 229748279 instead of 229748650)
Volume header needs minor repair
The volume Mac HD was found corrupt and needs to be repaired.
Error: This disk needs to be repaired. Start up your computer with another disk (such as your Mac OS X installation disc), and then use Disk Utility to repair this disk.

So I have run both Recovery HD and Single-User mode.

In Recovery HD, I Repair the disk. In Single-User mode I run /sbin/fsck -fy. I run each 3 times and they tell me that the volume Mac HD is ok.

I reboot and then run Disk Utility. The above message comes up. So it seems that on start up something is causing a problem. Any ideas?

edit - I did a format and the problem went away. However my Time Machine backup recreates the problem when I restore.