Got one of these scary messages about having to recreate everything and here is what I learned is that it appears only with Snow Leopard and what happens is that the backup is marked as bad and you get a choice, lose all your backups or else no more future backups 🙁 As Apple says

1. There is a magic file on the Time Capsule or what ever hard disk you use to keep Time Machine Backups called something like My Macbook.sparebundle. This is actually a complete file system. So what you have to do is drag this on top of the icon for the disk utility (isn't that confusing, because there seems to be no command in it.) according to JThon
2. The main reason for this is apparently according to a comment on Jtron's post:

An Apple “Genius” told me today that this is very common with the drive on another machine over wireless. I have an external Seagate drive connected to my airport and was backing up that way.

He explained to me that with a TimeCapsule you get a ton of extra cache (like server level amount) so there is a nice big buffer in case of a wireless drop of any kind. With ordinary external drives you do not get a large amount of cache, so it becomes very easy for TimeMachine to go through a wireless hiccup during backup and thus corrupt your backup files. Supposedly this is why Apple still doesn’t officially support 3rd party external hard drives over wireless for TM. Of course it doesn;t hurt that the best solution is to pay more money and buy a TC.

1. Then you can run Verify Disk on the bundle and see if it can be fixed. Apparently you can go harder core and use the Unix utility

So combining hdiutil and fsck_hfs we might have a way to fix the disk image. Note: Make sure you turn off Time Machine in the System Preferences panel. We don’t want Time Machine trying to mount our image and back up to it until we’re done making all the repairs.

First I ran hdiutil:

hdiutil attach -nomount -readwrite Bhaal_0011247e3338.sparsebundle

After a minute or two of thinking we had success:

/dev/disk1              Apple_partition_scheme
/dev/disk1s1            Apple_partition_map
/dev/disk1s2            Apple_HFSX

The next step was run fsck_hfs on the main volume.

fsck_hfs -rf /dev/disk1s2

-f is required to force a check since this is a journaled file system. I also used -r to have it rebuild the filesystem catalog for the “invalid sibling link” this is required (thanks Dan). At this point I went out for breakfast since I was running a disk repair utility over my wireless internet to my Linux SAMBA server. After coming back from breakfast we had success!