EDIT by Kelly: Though this guide was initially written to aid XBLA players in opening their NAT, much of this is applicable to PSN as well as XBLA. Open your NAT, make uPnP available, port forward or try a DMZ on your PS3. Doing these things will help ensure your router can play nice with others. Please post comments and suggestions in this thread!
-k
kelly wrote:
We definitely recommend taking whatever steps you can to change you NAT setting to open if it is currently STRICT as well.
Well, here are the steps! I was checking the Tech forums the other day and noticed a lot of people with network problems, so I decided to help them out.. If you're wondering how I know all this, well let's just say that one day I got annoyed with my NAT. So I spent the next 3 days learning. Also, if someone saw a thread about network problems, redirect them here!
Before I start, some people might not want to configure their router because they might be afraid of mucking their settings up. If that's the case, get your Caregiver/Dad or whatever to do it. Or don't change it and leave it as strict.
What types of NAT are there? What is NAT?
Network address translation. NAT. Is the process of modifying network address information in datagram packet headers while in transit across a traffic routing device for the purpose of remapping a given address space into another.
OPEN: Best NAT, it's what everyone wants. Open NAT allows for anyone to join you and you to join everyone else! This thread is about opening your nat.
MODERATE/STRICT: NAT types you don't want, you can't connect to other people properly and people start having network problems.
Who can connect to who?
Here is a nice little diagram showing who can connect to who:
As you can see, anything can connect to open. But Strict can't connect to moderate etc...
How to check if your NAT is open or not
Turn on your xbox360, and go to System Settings.
Open up Network Settings, and start Test Xbox LIVE connection.
If your receive a NAT warning, then your NAT is NOT open.
How to open your NAT -router-
UPnP
Every router has a different way to open your NAT, but all of them require ports to be opened or UPnP.
First off, you need to access your router. Enter it's IP address (whether it's 192.168.1.1 or something, you will have to find out) and enter your user name and password. (Usually admin admin unless you have changed it). If you can, in your router check your NAT.
First thing to try would be UPnP - Universal Plug and Play. Go into your routers settings and search around in Firewall or NAT settings. Make sure it's enabled. Some routers don't have UPnP but enabling this can open your NAT.
Here is a picture of my UPnP enabled.
Port forwarding
If UPnP doesn't work, leave it enabled and try port forwarding. Find "Port forwarding" or "Virtual servers" (It's called virtual servers on my router anyway..) or something like it. Also check the DHCP client list for your xboxs IP (usually called "unkown")
Open these ports.
* TCP 88* Microsoft's website says 80. Probably a typo.
* UDP 88
* UDP 3074
* TCP 3074
* UDP 53
* TCP 53
* PSN : UDP 3658
Here is MS explanation for opening ports.
http://support.microsoft.com/kb/908874
I have a picture that may help some of you who don't understand.
For those of you who have a really dodgy router. (Like me!) Look at this..
Each router is different when opening ports, so here's a good website to find out how to do it. (Make sure to find out your router model!)
http://portforward.com/routers.htm
Click on your router, and then scroll down to X and find Xbox360.
DMZ
That's right, most likely your router will have a firewall preventing people from connecting to you. Easy way to fix it. Take your xbox360 out of it!
This is quite simple, find out your xbox360s IP address and then add and apply.
I got a snip of my DMZ (I have not added my xbox to it, as my NAT is open.) But I put in the local IP of my xbox360.
Well, hopefully this helps people with NAT problems!
How to find out your IP address (not local)
I almost forgot, all those 192.168.?.? IP addresses you are looking at are all LOCAL, they are for your network and not for the internet! To find out your IP address click here!
http://whatismyipaddress.com/
Also, I recommend that you check your router's brand website and update your firmware. It's always good to have the latest.
Other information
I compacted this thread so that people don't have to read so much.
Happy holidays everyone! Remember, this is for your benefit! So don't spam.
If your still having problems, PM me. Remember, I couldn't cater to everyone's need. But that port forwarding website is cool. Also, I find that google helps. 
Please post here if you have more information to add, or if this is helpful/think it is helpful.
Important note: DO NOT TURN NETWORK ADDRESS TRANSLATION OFF.