Your NAT status has nothing to do with the game or your 360, it's all about your Xbox Live (network) connection.
There are three types of NAT connection settings: Open, Moderate, and Strict. You probably have either 'moderate' or 'strict' NAT settings, meaning you won't be able to connect to other players who are using Strict NAT settings.
I hope you'll understand this thread I'm giving you, because it explains everything about NAT connections, and how to change them.
http://www.rat*******s.org/viewtopic.php?t=32
If you don't understand anything about network connection, get some help from someone you know who does, or call a technician if it's that crucial.
Good luck.