It sounds like your new "modem" is not really a modem at all, but a combination modem/router or gateway type of device that combines the normal functions of a separate modem and separate router in one package.
Can you provide the make and model number of this device so that we can confirm on exactly what you have there?
You only want one router on a network provinding DHCP and NAT services, and if your new "modem" is doing this, then the AirPort Extreme needs to be configured in Bridge Mode to avoid IP address conflicts and NAT errors.
Check with your ISP to see if they can provide you with a simple modem.....not a modem/router or gateway.....that will allow the AirPort Extreme to correctly act as the router for your network, providing DHCP and NAT services.
This was the modem they would only allow, as I suppose it provided a higher level of bandwith.
Check with the ISP to see if the Arris modem/router can be configured to act as a bridge mode modem only. That would allow it to function as a simple stand alone modem, which is what you need.
Otherwise, you can try running the AirPort Extreme in the Double NAT error condition, but I do not recommend that you do this, as this will slow down your Internet connection and possibly create communication problems from one device to another on your network.
If you have not already done so, try plugging the AT&T Microcell into the Arris gateway to see that will allow it to function correctly.