Like many others I've had some trouble getting my XBox 360 to have an 'Open' NAT status so XBox Live chat (and potentially other functionality) would work correctly. I was having a hard time getting this right, even when I did what seems to be the most common solution to the problem: adding the XBox 360 to my router's DMZ.
Here's one additional step I had to do to get things to work, that I haven't seen mentioned elsewhere: In order to get your 360 into your DMZ you have to have a constant IP address for it. (Which plenty of sites did mention) HOWEVER, at first I was enforcing a consistent IP address for the 360 by setting the *360* to manually demand that IP address each time, rather than use DHCP. Doing that, my NAT kept staying at 'Strict'.
But, when I set my 360 back to using DHCP to get its IP address, and told my router to RESERVE the IP address I wanted for the MAC address of my 360, then POOF, my NAT setting went to Open! So, at least in my case, I had to not only add my 360 to my router's DMZ, but I also had to make sure that I enforced a consistent IP for it at the router instead of in my 360s network settings.