At least that were the first step I did last time. Despite my name were short already.
Not worked on Air right now.
The second step I recall , I clean the key chain access:
Anyhow the entry referred to the disk as old name and I changed under SL since ML does not offered the manual setup. I tried to let all access, but won't make a difference for me in keychain. Once Snow Lion asked again for the password due to the deleted keychain entries and I typed (note down that before I deleted the entry using show password checkbox) connection is succeed and now verify backup is in progress. So that works at least, without the power down of the capsule. Once the Pro is complete the capsule backup I enable the Air disk with new name since disk is now mounting under OSX, expected to mount for all OSX device. Hope it will ask for the password as well, than I knew the latest(renamed) backup disk is in use. I kept the Capsule base station password since that worked, just removed the disk entry from the chain.
I had this problem with my time capsule briefly, and it was cause by my setting up the disk on the time capsule with a differnet password than the accesspoint. I wanted the disk to have a different password to that the disk would not be accessible to everyone on my wifi network, but this prevented time machine from working with the disk, even though I configured the password from the same mac as I was trying to back up. I set it back to the accesspoint pw, and it worked fine.