[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!

• Connect your Backup Volume
• I recommend to disable your backups as it seems to disconnect your Backup volume.
• 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

• mount the sparsebundle as filesystem

  ~ # 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

• Monitor the progress of the file system check

  ~ # tail -f /var/log/fsck_hfs.log
  /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.
  ** The volume Time Machine-Backups appears to be OK.

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

• 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)
  ** The volume Time Machine-Backups could not be repaired.
          volume type is pure HFS+ 
          primary MDB is at block 0 0x00 
          alternate MDB is at block 0 0x00 
          primary VHB is at block 2 0x02 
          alternate VHB is at block 391877934 0x175b952e 
          sector size = 512 0x200 
          VolumeObject flags = 0x07 
          total sectors for volume = 391877936 0x175b9530 
          total sectors for embedded volume = 0 0x00 
  ~ # tail -f /var/log/fsck_hfs.log
  ** The volume Time Machine-Backups was found corrupt and needs to be repaired.
          volume type is pure HFS+ 
  /dev/rdisk1s2:  primary MDB is at block 0 0x00 
  /dev/rdisk1s2:  alternate MDB is at block 0 0x00
  /dev/rdisk1s2:  primary VHB is at block 2 0x02
  /dev/rdisk1s2:  alternate VHB is at block 391877934 0x175b952e
  /dev/rdisk1s2:  sector size = 512 0x200
  /dev/rdisk1s2:  VolumeObject flags = 0x07
  /dev/rdisk1s2:  total sectors for volume = 391877936 0x175b9530
  /dev/rdisk1s2:  total sectors for embedded volume = 0 0x00

• Finally, detach the file system

  ~ # hdiutil detach /dev/disk1s2

• 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

  DD.MM.YYYY HH:MM:SS

• Finally you want to change

  VerificationState

  2

  to

  VerificationState

  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.