Time machine & TC password problem

Today I used the Airport Utility to erase my Time Capsule and start fresh with a new MacBookPro. I then went into Time Machine in system preferences to select the Time Capsule as my backup disc. When I try to run a backup I get a pop up window telling me that the "network backup disk could not be accessed because there was a problem with the network username or password. Open Time Machine prefs to select the network backup disk and re-enter the correct username and password".

First of all, the Time Capsule itself doesn't have a "username". There's the name of the TC itself and then just a password. I even re-set the password to make sure I was using the right one, but this still didn't solve the problem. What else could it be?

Thanks,
Scott