Seems like the carrier has NAT as well. This happens if you do not have a public IP.
Maybe you can try opening some ports on the router which Xbox required to see if it works. Maybe it needs upnp?