Recently, speculating that updated software may have improved matters, I retried the multiple Mac setup that had previously failed. Matters had not improved. Adding my Mac Pro still caused a collapse on both Macs. This time, however, the error messages remained consistent: "Time Machine completed a verification of your backups. To improve reliability, Time Machine must create a new backup for you."
As explained in a helpful web article, the message means that the relevant sparsebundles are corrupt. Sometimes, attempting to repair the drive with Disk Utility may get things rolling again. It didn't do so for me. As before, I had to delete the backup files and start over. While the Verification message teases that starting over may prove successful, such was not the case. The error inevitably returned within a day or two.
Searching Apple Support Communities, I found several threads (such as Time Machine Verification Issue) that offered various suggestions on how to deal with this error, including how to potentially reconnect to an existing sparsebundle file rather than starting over from scratch. I was skeptical of this rather involved set of steps, as I suspected the data might still be corrupt even if the reconnect succeeded. So I never gave it a try. None of the other suggestions that I tried had any effect.
I was about ready to give up yet again. I had one remaining idea. Given that backing up just one Mac worked, I reasoned that the corruption was somehow precipitated by attempting to backup two Macs to the same drive. Perhaps, if I partitioned the drive, and backed up each Mac to a separate partition, Time Machine would consider this to be like one Mac per drive--and the error would be avoided. While a few forum postings suggested that partitioning would be more likely to cause trouble than eliminate it, I decided to give it a go. What the hell! If it failed, I would be no worse off than I already was.
It worked! I have now gone a month without any Verification (or any other) Time Machine errors. I've tested out restoring files from the Time Machine backups--and they succeed.
I can't offer any guarantees. I may still get an error tomorrow--or six months from now. However, given past history, I'm optimistic that I'm now home free. So... if you've been unable to get an AirPort-Extreme-connected drive to work with Time Machine and multiple Macs, partitioning may be the solution. Just make sure you have a secondary backup before you start experimenting.
Sign up for Computerworld eNewsletters.