Did you do the factory reset of the AE?? That is necessary. The AE keeps too many values from the last setup to easily move to a new configuration.
The quick method of factory reset.
Please look at Time Capsule (TC) as the same thing as the Extreme.
Power down the TC.
Hold in reset. and keep holding it in. Be Gentle! It is a tiny surface mount switch with a plastic lever.. Attempting to push it out the other side of the TC will not make the switch turn on better.
(I fix TC and have several reset levers bent over and jammed or broken off).
Power on the TC.. remember with the reset held in.. this needs three arms.. a friend or power switch you can get to with your feet..
Keep holding in reset for about 10sec until the front LED flashes rapidly.
Release reset and wait .. the boot will be slow as it deletes previous setting.. only from router side and pulls out the factory defaults. No files are deleted on the hard disk.. but the name of the TC may change.
The power cycle of the cable modem is very important.. it has to be off completely for 20min and sometimes longer.. overnight. Some battery backup version modems do not go off without removing the battery.. even unscrew the coax cable.
Make sure when you power up the modem only the AE is plugged in. Make sure the AE is set to router mode.. DHCP + NAT.. and is plugged in WAN port to the LAN port of the modem.
If you keep having trouble post again..
We need to know the model of the AE and firmware it is running.
Also what version utility on what OS you are setting it up from.