Double NAT

Sounds like you have a second device doing NAT on your network. It's hard to know without knowing your setup. My guess would be you have a modem that's also doing NAT.

Either disable NAT on the modem, or set up the APE to "bridge mode".

I have this and ignore it. I have a uverse gateway router doing NAT and on my internal wired network I connect to my AE via the AE WAN port....which in turn NAT's my wired IP range to a new wireless subnet. i.e. wired subnet 192.168.1.x and wireless is 192.168.2.x. This also provides a good broadcast separate from my wireless and wired devcies as the AE WAN port blocks multicast and broadcasts that would othersiwe congest my wireless network.

I don't have your modem but from looking online there is an option here:

http://s1182.photobucket.com/albums/x441/rajah31/FritzBox/?action=view&current=N AT.jpg

Yes that's it.

Yes that's normal. They are related. You should only have one device on your network doing NAT and assiging IP addresses.

Are you able to keep NAT disabled and the DHCP enabled? Keeping it on should not be a big issue.

You probably need to resart the APE after you do this, may be that's why you had no internet.

Your Fritzbox should still be accesible no matter what. Write down it's IP address.