The TC is very hard to just move.. it retains too much of the old network setup.. buried deep in the bowels of the firmware configuration files.. or even on the hard disk special partitions used by the TC.. invisible to you btw.. !!
Do a factory reset and setup from scratch.
That factory reset will have no affect on your backups.. even if you rename the TC.. not a bad things since you also want clients to respond to the new network.. simply reset TM to the new TC name and location.
See A4 here.
http://pondini.org/TM/Troubleshooting.html
Factory reset.
The Factory Reset Gen1-4.
Unplug your TC. Hold in reset. and power the TC back on.. without releasing reset for about 10sec. When the status light flashes rapidly; release it.
Be Gentle! Feel the switch click on. It has a positive feel.. add no more pressure after that.
TC will reboot after a couple of minutes with default factory settings and will wipe out previous configurations.
No files are deleted on the hard disk.. No reset of the TC deletes files.. to do that you use erase from the airport utility.
Factory reset Gen 5
Hold in reset for about 5sec until the status light flashes quickly.
If your AirPort Time Capsule still doesn’t respond, do a similar reset to the Gen1-4.
Unplug your AirPort Time Capsule .. hold in reset and power the TC back on.. without releasing the reset.. wait until status led flashes rapidly.