No DNS and Double NAT

Hello, I've recently encountered a very frustrating bug in my system that I could use some help troubleshooting. I've read several similar posts, some are resolved while others are not, however none of the resolutions have worked for my situation. Here it goes:

I have an old macbook pro, a new macbook air, a white macbook and 2 iPhone 4s's all connected to the internet via WiFi through an AirPort Extreme. The AE is connected to a cable modem which has internet service through Cablevision in NY. There is also an AT&T Microcell hooked up to the AE to boost my cell signal. All of this equipment has been working flawlessly together for a long time. Until recently. It could have started after an update, there have been several lately on all of the equipment including the firmware in the AE. Anyway, I'll be connected without any issues - all lights green and happy - when suddenly, the internet will drop off and the AirPort Utility will pop up and warn me that:

1) On the "internet" icon, it will say "disconnected"

2) On the AE icon, it says "No DNS server and Double NAT"

After a few minutes and nothing done on my part, the lights turn green, the internet reconnects and all is well again.

This happens frequently and is really beaching a nuisance. Due to the frequency of the disconnection, I can no longer download a large file, update, or anything. Streaming video is impossible.

So far, I have tried bridge mode and cycled the power in the order recommended to no avail. When I do that, the AE turns green, but the internet says "not connected". I have also read that there might be too many IP addresses which is not sitting well with my ISP, so I disconnected everything including unplugging the Microcell. Lastly, there are no other wireless phones or devises in the house. All to no avail.

I should also mention that this began occurring on my Time Capsule, which I replaced with the AE in an attempt to fix this issue.

Any help would be greatly appreciated.

Joe