Time Capsule/ Endless Preparing - no backup

I've seen similar threads and I believe that I've tried all of their fixes.

I'm seeing the following errors in the console:
Aug 7 10:30:34 HomeMac /System/Library/CoreServices/backupd[191]: Waiting for index to be ready (909 > 0)
Aug 7 10:30:34 HomeMac mds[33]: (/Volumes/Backup of HomeMac/.Spotlight-V100/Store-V1/Stores/F9F6764C-F1D9-46D4-804E-4CFDC556F1E8)(E rror) IndexCI in ContentIndexOpenBulk:No index
Aug 7 10:30:34 HomeMac mds[33]: (/Volumes/Backup of HomeMac/.Spotlight-V100/Store-V1/Stores/F9F6764C-F1D9-46D4-804E-4CFDC556F1E8)(E rror) IndexCI in CIMetaInfoCreate:Tried to create index when index already existed /Volumes/Backup of HomeMac/.Spotlight-V100/Store-V1/Stores/F9F6764C-F1D9-46D4-804E-4CFDC556F1E8
Aug 7 10:30:34 HomeMac mds[33]: (/Volumes/Backup of HomeMac/.Spotlight-V100/Store-V1/Stores/FB0AF823-52BC-455D-9BE4-5267CC68CEB9)(E rror) IndexCI in open indexfile:bad file size: 16, min size 4096, 0.indexHead
Aug 7 10:30:34 HomeMac mds[33]: (/Volumes/Backup of HomeMac/.Spotlight-V100/Store-V1/Stores/FB0AF823-52BC-455D-9BE4-5267CC68CEB9)(E rror) IndexCI in ContentIndexOpenBulk:0.indexHead invalid, will try to recover
Aug 7 10:31:00 HomeMac com.apple.launchd[1] (0x109db0.cron[397]): Could not setup Mach task special port 9: (os/kern) no access
Aug 7 10:31:04 HomeMac /System/Library/CoreServices/backupd[191]: Waiting for index to be ready (909 > 0)
Aug 7 10:31:04 HomeMac mds[33]: (/Volumes/Backup of HomeMac/.Spotlight-V100/Store-V1/Stores/F9F6764C-F1D9-46D4-804E-4CFDC556F1E8)(E rror) IndexCI in ContentIndexOpenBulk:No index
Aug 7 10:31:04 HomeMac mds[33]: (/Volumes/Backup of HomeMac/.Spotlight-V100/Store-V1/Stores/F9F6764C-F1D9-46D4-804E-4CFDC556F1E8)(E rror) IndexCI in CIMetaInfoCreate:Tried to create index when index already existed /Volumes/Backup of HomeMac/.Spotlight-V100/Store-V1/Stores/F9F6764C-F1D9-46D4-804E-4CFDC556F1E8
Aug 7 10:31:04 HomeMac mds[33]: (/Volumes/Backup of HomeMac/.Spotlight-V100/Store-V1/Stores/FB0AF823-52BC-455D-9BE4-5267CC68CEB9)(E rror) IndexCI in open indexfile:bad file size: 16, min size 4096, 0.indexHead
Aug 7 10:31:04 HomeMac mds[33]: (/Volumes/Backup of HomeMac/.Spotlight-V100/Store-V1/Stores/FB0AF823-52BC-455D-9BE4-5267CC68CEB9)(E rror) IndexCI in ContentIndexOpenBulk:0.indexHead invalid, will try to recover

Things that I've tried:
- Erase disk both with "quick" and "zero out" options.
- Restore defaults
- Roll back firmware to 7.4.1
- changed time machine to use different disk, successful backup to that disk, set back to time capsule.
- tried to add "Backup of HomeMac" and "TimeCapsule" to the spotlight privacy settings. These settings are lost at reboot.... and if I don't reboot it says that it fails to mount "Backup of HomeMac". Likely because it is already mounted?
- I have 2 macs that backup to this time capsule. It has worked for several months. Now doesn't work for either. One is running 10.5.8.. the other is running 10.5.7.
- Tried to use DiskUtility on the sparsebundle. It looks clean after a reboot, but then timemachine won't run... possibly because it is already mounted?? It looks corrupted in DiskUtility after I quit the time machine backup. In any case, I keep "erasing" the time capsule hard drive, so if there is a problem with the bundle, it is created from scratch and still has the problem.
- verify permissions on my Mac's main HD.
- changed the name of the TimeCapsule.


I think that is all. I get the same error every time. I don't know if this is a spotlight issue or a time capsule issue. It does affect 2 macs with different OS versions (10.5.7, 10.5.8), so I assume that it is the time capsule.

One other possibly unrelated issue: When I used to run time machine the backup volume would be mounted with my name. Now it just says the network name. (i.e. it used to say something like "Backup of John Smith's Mac" and now it says "Backup of HomeMac") I assume this is unrelated, but I figured I would mention that too.

Anyone have any ideas?

Thanks.