Time Capsule Setup Woes
If the old Airport Express was connected directly to your cable/DSL modem and the new Time Capsule replaced it (again, directly connected), you may need to reboot the modem (generally by unplugging it and plugging it back in, maybe holding down the reset button) to reset its DHCP. You may also need to do this in a particular order, generally 1) shutdown Time Capsule, 2) reboot modem, and 3) restart Time Capsule.

Reason: some broadband modems seem to only assign one internal IP at a time and only check for a device on startup.