802.11/n Extreme (now on DSL) + Xbox Live = no

Today I downgraded to AT&T's 6Mbit DSL package from my Comcast 12Mbit with powerboost package due to cost. I never had any complications running Xbox Live wirelessly from my Airport Extreme, yet as soon as I made the transition to AT&T I ran into all sorts of problems with NAT settings and what not. I've spent the last couple of hours sifting through different forum posts on several websites that were discussing similar issues, but none of the solutions people have offered have helped me. I've tweaked my router settings at least a half dozen times with no success... I keep getting the same results when I test my connection on my Xbox (it says it's connected to Live but I'll have difficulty joining games because my NAT setting is "strict").

Has anyone out there had a similar experience? I've tried everything I can to alter my NAT settings so that they're more or less "open"... I tried putting the router in "bridge mode" but that made matters worse and I had to restore factory settings. I'm at a loss about what to do, I didn't have a single problem with Comcast, it was plug-and-play... now everything's jammed up with AT&T.

Any suggestions would be appreciated. Thanks guys.

EDIT: I've manually given my Xbox a static IP address and entered that address into the "Enable default host at" box under Internet --> NAT settings. Still no luck, my Xbox says it still has a "strict NAT". I'm out of ideas...