[This is an extract from Fix Time Machine Sparsebundle NAS Based Backup Errors by Garth Gillespie]

This is work in progress! Not all steps are verified yet!

1. Connect your Backup Volume
2. I recommend to disable your backups as successive tries seem to interfere with the recovery process.
3. Start a shell (Terminal Window) with root permissions and recursively clear the user immutable flag:

   ~ # chflags -R nouchg /Volumes/Backup_Volume/MyHostname_YYYY-MM-DD-HHMMSS.sparsebundle

4. attach the sparsebundle as volume without mounting

   ~ # hdiutil attach -nomount /Volumes/Backup_Volume/MyHostname_YYYY-MM-DD-HHMMSS.sparsebundle
   /dev/disk1              Apple_partition_scheme
   /dev/disk1s1            Apple_partition_map
   /dev/disk1s2            Apple_HFSX
   ~ #

   Use the partiion listed as Apple_HFSX in the following steps (i.e. replace /dev/disk1s2 the your partition). This will implicitly start a file system check. As checked with ps, the actual command run seems to be
   /System/Library/Filesystems/hfs.fs/Contents/Resources/../../../../../../sbin/fsck_hfs -y /dev/disk1s2

5. Monitor the progress of the file system check

   ~ # tail -f /var/log/fsck_hfs.log
   /dev/rdisk1s2: fsck_hfs run at DDD MMM DD 'HH:MM:SS YYYY
   /dev/rdisk1s2: ** /dev/rdisk1s2 (NO WRITE)
   /dev/rdisk1s2:    Executing fsck_hfs (version diskdev_cmds-491.6~3).
   QUICKCHECK ONLY; FILESYSTEM DIRTY
   
   /dev/rdisk1s2: fsck_hfs run at DDD MMM DD 'HH:MM:SS YYYY
   /dev/rdisk1s2: ** /dev/rdisk1s2
   /dev/rdisk1s2:    Executing fsck_hfs (version diskdev_cmds-491.6~3).
   ** Checking Journaled HFS Plus volume.
   ** Detected a case-sensitive volume.
   ** Checking extents overflow file.
   ** Checking catalog file.
   ** Checking multi-linked files.
   ** Checking catalog hierarchy.
   ** Checking extended attributes file.
   ** Checking multi-linked directories.
   ** Checking volume bitmap.
   ** Checking volume information.
      Invalid volume file count
      (It should be 2706734 instead of 2626590)
      Invalid volume directory count
      (It should be 277698 instead of 274514)
      Invalid volume free block count
      (It should be 28460131 instead of 29740128)
      Volume header needs minor repair
   (2, 0)
   /dev/rdisk1s2: ** Repairing volume.
   ** Rechecking volume.
   ** Checking Journaled HFS Plus volume.
   ** Detected a case-sensitive volume.
   ** Checking extents overflow file.
   ** Checking catalog file.
   ** Checking multi-linked files.
   ** Checking catalog hierarchy.
   ** Checking extended attributes file.
   ** Checking multi-linked directories.
   ** Checking volume bitmap.
   ** Checking volume information.
   ** The volume Time Machine-Backups was repaired successfully.

   (If something goes wrong and you have to start over, you need to clear the user immutable flag again.)

6. When done (successfully), run disk repair:

   ~ # fsck_hfs -drfy /dev/disk1s2
   ** /dev/rdisk1s2
           Using cacheBlockSize=32K cacheTotalBlock=8192 cacheSize=262144K.
      Executing fsck_hfs (version diskdev_cmds-491.6~3).
           Journal replayed successfully or journal was empty
   ** Checking Journaled HFS Plus volume.
   ** Detected a case-sensitive volume.
   ** Checking extents overflow file.
   ** Checking catalog file.
   ** Rebuilding catalog B-tree.
   hfs_UNswap_BTNode: invalid node height (1)
   ** Rechecking volume.
   ** Checking Journaled HFS Plus volume.
   ** Detected a case-sensitive volume.
   ** Checking extents overflow file.
   ** Checking catalog file.
   ** Checking multi-linked files.
   ** Checking catalog hierarchy.
   ** Checking extended attributes file.
   ** Checking multi-linked directories.
           privdir_valence=24850, calc_dirlinks=101703, calc_dirinode=24850
   ** Checking volume bitmap.
   ** Checking volume information.
   ** The volume Time Machine-Backups was repaired successfully.
   ~ # 

7. Finally, detach the file system

   ~ # hdiutil detach /dev/disk1s2

8. When complete, you need to edit an plist file within the sparsebundle that records the state of the backup. Within the sparsebundle open the file com.apple.TimeMachine.MachineID.plist with the Plist Editor. Remove the Entry

   RecoveryBackupDeclinedDate

   Date

   DD.MM.YYYY HH:MM:SS

9. Finally you want to change

   VerificationState

   Number

   2

   to

   VerificationState

   Number

   0

Now you can eject the network share and have Time Machine give it another go. After the (long) verification step, backups should proceed once again.