I get messages about needing to start a new backup frequently, and because I backup a lot of data this takes forever and is really annoying. I have found the following method for repairing a TM volume:
chflags -R nouchg /Volumes/[yourshare]/[whatever].sparsebundle
hdiutil attach -nomount -noverify -noautofsck /Volumes/[yourshare]/[whatever].sparsebundle
fsck_hfs -drfy /dev/disk3s2
In the sparsebundle file is a plist called “com.apple.TimeMachine.MachineID.plist”. Edit it and remove “RecoveryBackupDeclinedDate” and the corresponding date, and change “VerificationState” to 0.
You can also use DiskWarrior on Time Machine volumes from DiskWarrior’s file menu -> “Rebuild Disk Image”.