I tried a few popular routers / modem-routers. Only Time Capsule and AirPort series give me "double-NAT" problem!
mcpo1234, your situation is easy to fix. Just turn off the DHCP and NAT features from your modem (i.e. using "bridge" mode) and let your Time Capsule be the DHCP and NAT server.
In my case, it's complicated because the Internet is being provided as an private WAN which I cannot turn off their DHCP and NAT. Thus "double-NAT" error appears and my Time Capsule cannot connect to the Internet under "DHCP Only", or "DHCP and NAT" modes. But when I use "Bridge" mode, the Intranet only provides me one IP address and each time I can only EITHER use my Mac, OR my iPhone, NOT together.
My work-around will be: I connect the private WAN to my Time Capsule and from my Time Capsule to cascade another router (e.g. D-Link, Belkin or NetGear which supports double-NAT). Why do I do this? Becasue the WiFi network provided behind DHCP and NAT is well-secured. Under "Bridge" mode, my WiFi network is sharing the same wireless network behind, and thus unsecure! But the problem is: the Time Capsule drive (though password protected) is fully exposed in the WAN network because it's only bridged, not protected by DHCP and NAT. Did Apple's network engineers think about it?