If you see a dialog like this, your backup may be broken or just have a little problem with the disk image. So usually we try to repair it instead of starting over. This are the steps necessary:
First turn of backups and mount the Time Machine disk and check what the name of the disk and the sparse bundle inside is, so you can adjust the names. hdiutil will return the disk number, which must be used for the next two calls:
After fsck_hfs repaired the disk image on your time machine, you may need to remove the nouchg flag for the sparse bundle:
sudo su -
hdiutil attach -nomount -noverify -noautofsck /Volumes/DiskName/BackupName.sparsebundle
fsck_hfs -dfy /dev/diskXs2
hdiutil detach /dev/diskXs2
In the plist file inside the bundle, you may need to remove the decline date where the backup was marked broken:
chflags -R nouchg /Volumes/DiskName/BackupName.sparsebundle
And set the VerificationState back to zero:
If you did all the steps, you can enable backups again and let it continue with the same time machine sparse bundle.
We did those fixes a few time already and usually fsck reported just a minor problem.