When you move the network.. do a factory reset on the TC and do the setup again.. this is absolutely normal. A reset will do no harm to the backed up material on the hard disk.
The quick method of factory reset.
Power down the TC.
Hold in reset. and keep holding it in. Gently it is a tiny surface mount switch with a plastic lever on a plastic hinge.. Attempting to push it out the other side of the TC will not make the switch turn on better.
(I fix TC and have several reset levers bent over and jammed).
Power on the TC.. this needs three arms.. a friend or power switch you can get to with your feet..
Keep holding in reset for about 10sec until the front LED flashes rapidly.
Release reset and wait .. the boot will be slow as it deletes previous setting.. only from router side and pulls out the factory defaults.
And if you use 6.3 airport utility you may need to turn on ipv6 local-link.
I have frequently traveled with my Time Capsule, and it is definitely not normal to have to do a factory reset when changing internet service providers.
On older MacBooks, the IPv6 setting was OFF, and as LaPastenague pointed out, you have to change the IPv6 setting to "Link-local only." After recently updating AirPort utility to 6.3, I had to do this on both my MacBook and my iMac.