Start from C12 here.
http://pondini.org/TM/Troubleshooting.html
No luck..
what OS are you running??
Power down the whole network.. and all the clients.. everything..
Reboot in order..
Modem.. wait 2min
TC.. wait 2min
Clients..
Now see if the problem has been fixed.. if not you are going to need to do something major.
Redo the setup.. esp. important for mavericks.. start with reset the TC to factory.
Universal Factory Reset.. any model TC or AE.
Unplug your TC/AE from power or turn off at the power point.
Hold in reset. and power the TC/AE back on.. all without releasing reset and keep holding in for about 10sec. (this is often difficult without a 2nd person or a 3rd arm).
Release it when the status light flashes rapidly. If it doesn’t flash rapidly you have missed it and try again.
Note..
Be Gentle! Feel the switch click on. It has a positive feel.. add no more pressure after that.
TC/AE will reboot after a couple of minutes with default factory settings and will wipe out previous configurations of the router.
No files are deleted on the hard disk in a TC.. No reset of the TC deletes files.. to do that you use erase from the airport utility.
Redo the setup but this time use SMB naming..
Short, less than 10 characters is great.. less than 20 as max.
No spaces.
Pure alphanumeric.
Reset TM.. see A4 here.
http://pondini.org/TM/Troubleshooting.html
Point it to the newly renamed TC..
If it still fails..
I recommend you rename your computer and delete the existing backup if you don't have enough space.. but if you simply rename the computer it should start a new backup, although you might be able to inherit the old one.. see B6 in pondini.
Change the computer name.. see C9 for why this is important. You change under sharing in Preferences.. again make the name short, no spaces and pure alphanumeric.