I get this error and was wondering if anyone knew what the issue might be.
It is supposed to be backing up to Time Capsule but not sure if it's ever worked. It's actually not mine but if there was something quick to check, I'd appreciate it.
Try to setup Time Machine from scratch:
Turn TM off
Turn it back on. Select a disk (the Time Capsule should show up ok).
You should get a message that TM is starting in 2 minutes..
If that has problems, can you post here again..
edit 1 was an issue with computer name needing to be set (see in comments)
You can also try to use Airport Utility. run that, find the Time Capsule, and choose the Disk option. Then you can Erase Disk..
I hope this helps.