abombaci's posting helped me.
I'm sure there are many factors when troubleshooting these sorts of things because there could always be issues layered on top of one another.
I received this error with the following scenario:
- Mac mini ethernet connected to my Time Capsule on OS 10.8.3.
I first tried rebooting both the Mac Mini and the Time Capsule (each individually and then both at the same time). Neither option worked for me.
Following abombaci's recommendation, I did notice that my Time Capsule was listed under "SHARED" items in Finder. Although it did not show as a mounted hard drive (that would allow me to Eject it), upon selecting the Time Capsule, I noticed that it was still "Connected".
I then chose to "Disconnect" the Time Capsule and then re-attempted to start a Back Up on Time Machine. This seemed to do the trick for me.
Basically, my Mac Mini seemed to think that the Time Capsule was already connected to my system and had taken up a particular IP address so that when it attempted to reconnect again, it got a wee bit confused. Not a techie explanation but one that seemed to make sense to me.