I had the same problem suddenly, getting error 6584 and the message that time machine could not complete the backup because the xx.sparsebundle was already in use.
It seemed to be in use on drive x-1, i.e., there seemed to be 2 drives with the same name. And sometimes I could see both of them in the shared part of the finder window sidebar.
So after reading through all these messages and your excellent web site, I deleted the library file com.apple.TimeMachine.plist and reset time machine. But it still would not work because the sparse bundle was already in use.
I read solutions on other forums as well. One simple choice was to disconnect all user from the Time Capsule.
But with Mountain Lion and the latest airport utility, there is no option anymore for doing that.
MacUserRWB (in a previous comment about airport utility) noticed that he had file sharing turned off on the disks tab of for one computer and thus that computer could not backup anymore. This gave me the idea to turn off file sharing to force the disconnect of users. The time capsule updated itself, I turned file sharing back on, the time capsule updated itself once more, and I wass then able to make the backup.
I don't know why the problem happened in the first place. Was it because I had very little room on the time capsule disk, or was it because I switched from ethernet to wireless to ethernet, or was it something else?