I had issues awhile back trying to connect my Xbox360 with wireless N adapter (and Xbox360 S) to my older Airport Extreme router. I had to use ethernet, which was no problem since it was a 10-foot run.
I tried again to get wireless connectivity. If I remember correctly, I initially had it connect to the Airport via N on the 5 GHz band. I wound-up having to scale it back to G on 2.4 GHz band, and that worked.
Now that I have a dual-band capable Airport Extreme, my 360 S connects without issues. (Setting: 802.11n only 5 GHz, 802.11b/g)
Also, according to Xbox.com, there is connectivity problems with AT&T Uverse users and Xbox Live.
»support.xbox.com/en-US/xbox-live ··· e-status
Warning: This message is protected by ROT-26 encryption. Permission is required to decrypt, reverse engineer, read silently, read aloud, print, copy, post, email, broadcast, save, store, backup or delete.