OK, with the help of Applecare I was finally able to fix my issue. I started getting the message daily that says “Time Machine completed a verification of your backups ‘xxx Time Capsule.’ To improve reliability, Time Machine must create a new backup for you.” but every time I tried creating a new backup it failed again. In my case it turned out there was a corrupted backup image which Time Machine was unable to delete. Here’s how we found it and worked around it:
First, go to Time Machine Preferences and turn off Time Machine (for now). Now open a new Finder window and under “Shared” in the left pane select the Time Capsule. It has just one folder called “Data”—double click it to open it. Here we found one file called "Jim's iMac.purgeable.purgeable.purgeable.purgeable.purgeable.purgeable.sparsebundle”. (I think maybe every time it tried to delete it it must’ve added another “purgeable” in the filename.) Select it and from the action button in the toolbar select “Move to Trash” and confirm when prompted. Again, in my case it would not delete this file, complaining that “The operation can’t be completed because the item “bands” is in use.” What is this “bands” file? No idea. Anyway again from the Action button we created a new folder called “archive backup” and then moved this file we were trying to delete into this file. After that we went back to Time Machine Preferences and turned it back on, then from the menu bar I selected “Back Up Now” and it backed up successfully. Yea!
Now, since this purgeable.sparsebundle file couldn’t be deleted I took the extreme effort to get rid of it permanently by executing the following steps. First, turn off Time Machine on ALL computers being backed up by the Time Capsule. I back up three computers to this Time Capsule so I had three sparsebundle files on my Time Capsule that didn’t say “purgeable”. So next I copied each of these sparsebundle files onto another drive (I just happened to have a new 3TB drive I had gotten the day before). Copying these files took a long, long time (i.e. over 24 hrs.) because of their file size but also the fact that it had to copy them over the wireless connection to the Time Capsule. I suppose you could skip this step if you don’t care about historical backups but I didn’t want to risk losing that because, well, you never know.
After all of the sparsebundle files were copied to a backup drive then I opened Airport Utility. Click Edit to edit the Time Capsule and then click on the Disks tab. Select the “Data” partition and click the “Erase Disk….” button. Once the Time Capsule drive was erased then I copied all of the sparsebundle files from the spare drive back to the Time Capsule. Again this took a long time. Once the files were copied back then I turned re-enabled Time Machine in my System Preferences on my iMac and then started a new backup. Success! Then I re-enabled Time Machine on the other two computers backed up by my Time Capsule and verified that they are each backing up successfully. I’ve now been backing up for two weeks without a single error. Hope this helps!