Time Machine no longer works after upgrading AEBS

I just upgraded my two year old AEBS to the latest version of the AEBS (simultaneous dual band). I configured the new AEBS with the same configuration as the old one. But now Time Machine will not back up to the external USB HD that I have plugged into the AEBS. I get the following error:

Time Machine could not complete the backup.
The backup disk is not available.

The disk is visible in AirPort Utility and is connected in the Shared section of Finder. The disk is also visible in Time Machine but it just flops out with the above error when trying to run a backup. Everything worked perfectly in the old AEBS.

Time Machine works when the USB disk is plugged directly into my Mac. I've tried using Disk Utility to wipe and reformat the USB disk, all to no avail. I know everything should "just work" but it clearly isn't!

Any ideas on what I could try?

OK I figured this out. When looking at the AEBS logs I noticed a login entry for when I selected the disk to use and the login was successful. However, when I went to run the backup the login failed. Therefore, I stopped Time Machine and opened the Keychain Access app and deleted all passwords that had been saved for the AEBS. I then restarted Time Machine, selected the disk and voila, everything is working again!

Just thought I'd let you know.