It is probably something silly, but...
I have just set up a Time Capsule, and it connects to the outside world, and one of the two Macs in the house can connect to it at a time - but not both.
Is there a setting I'm overlooking somewhere?
(I have the up-to-date Airport Utility, 5.4.2, and I upgraded the Time Capsule firmware to 7.4.2. The machines are a Mac Mini and a MacBook Pro. At some point, I want to get my Windows XP laptop - work machine - to connect too; that has problems with not supporting the more advanced network security that the Macs support.)
Something wrong at your configuration. I have a Time Capsule too. My Mac Mini wired to it and I have several Windows machine - laptop, PDA, Smartphone - which are connecting wirelessly. Same time without problem.
Do you have MAC address filter turned on? Which ports are you using for the connection? Ethernet or WiFi? What security settings are you configured in the router?
What is in the log? (in the Airport Utility: Manual setup/Advanced/Statistics/Logs and Statistics/Logs)
You should also check the DHCP server (Airport Utility: Internet/DHCP). Difference between DHCP Beginning address and DHCP Ending address should be more than one. It is only relevant if your computers are using DHCP to get IP address of course.
Usually your router is going to be in whats called Bridge Mode, It only allows 1 device to connect at a time and can cause strange errors about the IP address.
It is a setting in Airport Utility. Manual Setup. Its located on the Internet Tab. Connection Sharing. If connection sharing says "OFF" Bridge Mode. Switch it to Share a Public IP address and update it. It is a common setting that can get switched over.