Setting up Time Capsule was as painless and quick as the AirPort Extreme. In about ten minutes I was able to switch my MacBook Pro over to using the Time Capsule. A few minutes later and all the MacBooks along with my AppleTV was switched as well.
Initially everything seemed to go without problem. Internet access was working, I was using the AirPort Utility to tweak the settings to my liking, and I was able to enable Time Machine to get a backup started. Life was good.
Then things went to crap. Neither laptop was able to complete a single backup, consistently popping up the Time Machine Error dialog (see above). The backup process was stopped while the dialog was up, meaning user intervention is needed when this glitch came up, which is did multiple times. I also noted that while both laptops were backing up, my AppleTV behaved rather poorly. My assumption is the multiple backups saturated the Time Capsule’s throughput, especially considering both backups were first-time full snapshots, on the order of tens of gigabytes each.
After an over-night of no backups, I’m going to try disabling Time Machine on one laptop and see if the multiple clients was causing any problem for Time Capsule.