NAT Related Problems

There's some conflicting information about the ports you need open/forwarded to your Xbox.  The Microsoft article doesn't list the correct ports or protocol.  Often times you end up getting a NAT related message.

NAT Mesages:

Open
This means that you router has optimal settings, and you should not run into any of the issues described in this article.

Moderate
This means that you can talk to other players who have open or moderate NAT issues, but you cannot talk or play with users who have strict NAT issues.

Strict
This means that you can talk only to other players, but you cannot talk to players who have moderate or strict NAT issues.

If you get a message regarding "Moderate" or "Strict" NAT, you need to forward the ports below to your Xbox.

Ports that need forwarded to your Xbox 360 console:

Port 88 TCP & UDP
Port 3074 TCP & UDP
Port 2074 TCP & UDP

You will need to configure your router to forward those ports to your Xbox.  Check out PortForward.com for help in doing this.  Most people are using DHCP from the router to assign an IP address to their Xbox.  I would suggest you configure a static IP address on your Xbox before you forward your ports.  Navigate to the network settings under the system settings menu.  Here's a good article on how to get that done.

References
Xbox 360 Networing Concepts
Xbox 360 Understanding NAT