I have (or had, until ATT sold out to Frontier in CT) ATT Uverse.
Here's how I set mine up:
First, I think you will want to connect via a WIRED connection to the Uverse residential gateway, and then....
Turn OFF wireless on the residential gateway (Uverse "modem/router").
Next, connect the Airport Extreme to one of the LAN ethernet ports on the residential gateway.
Now, you should disconnect from the residential gateway, and connect via ethernet (for the moment only) to the AE.
Got a good wired connection?
Fine, open Airport Utility.
In the Base Station tab, give it the name and password you wish.
In the Internet tab, choose DHCP.
In the Wireless tab, choose to "create a wireless network", and set up the rest of the choices in that panel as you wish.
Now move to the "Network" tab and for "Router Mode", choose "Off (Bridge Mode)".
Save the changes.
Set up this way, the residential gateway does the NAT and serves as the basic (wired) router. The Airport Extreme has NAT turned off so you don't end up in a "dual NAT" situation, which causes problems for some folks. AE still works as a second router/switch and gives you best wireless speeds.
That seems to work fine for me.
If I've made an error, I'm sure others will jump in with corrections...