Somehow I'm glad to see I am not alone with such problems.
My Airport Extreme 5th gen stopped pulling an IP from my cable modem from the 10th of nov (the release date of FW7.6). Before it worked for months without any problem at all.
My setup: Motorola surfboard cable modmen --> AE which shares one IP --> NAS over eth, MBP and 2 PCs over WLAN
I tought it would be wise to upgrade after the AE failed, so I did. Even without internet connection, the AE did the upgrade which should mean it already downloaded it somewhere before I told it to upgarde.
After the upgrade same problem, no internet connection and no DNS servers available.
I connected my MBP and PC directly to the cable modem -> OK
I resetted the whole setup and hooked the AE again. Airport utility gave the same warnings, found a AE with problems, no internet and DNS servers.
Then I configured the AE in bridge mode, to share the IP he should get from the modem over WLAN -> OK??
So I got it working, but not in the mode I wanted it to work as my NAS is not accessible in this way.
In order to be 100% sure to blame the modem or AE, I hooked up the AE in router mode (share 1 IP) at my fathers place and father in laws place, who both have the same ISP but other versions of the cable modem ->OK
As it works at their place, I tested again at my place in router mode -> still not OK
Then contacted tech support of the ISP to check if the modem is OK and they told me the modem works fine as they could see I was still able to pull IPs out of the modem in bridge mode.
They asked me to hook up the AE again in router mode to check what could be wrong.
They told me the AE does a DHCP request, the cable modem answers, but then the AE does an other request, over and over again, without giving the modem the right answer to proceed the DHCP.
I really tried every possible way to solve it: downgrade to 7.5.2, upgrade again to 7.6, owngrade to 7.5.2, upgrade again to 7.6, hard reset of the AE, factory reset of the AE, rebuilding the network from scratch, replacing cabled, ... to much time has been waisted
Bottom line:
The ISP says their modem works fine.
Apple store told me the AE works fine as it works on the other modems.
At the moment I use the AE in bridge mode, so no NAS and with only 2 devices at the same time as the modem can only give 2 IPs. I guess I have to wait for next FW update?