[quote name='Oxygen']Is Universal Plug and Play (uPnP) enabled on both the router and the PS3? I think it is enabled by default on the PS3. That might make it easier for the PS3 to get the ports open that it needs.[/quote]
uPnP is BAD. You don't need it for Nat type 2 (Which is the good one, means you have a router but it shouldn't be interfering). Did you open and forward the ports to your PS3's IP address? To do this, you'd go into the Gaming section (If you have a linksys), and find all the ports that sony needs, which are:
TCP Ports: 80, 443, 5223, and 10070 - 10080
UDP Ports: 3478, 3479, 3658, and 10070
and forward them to an address such as 192.168.7.199.
Next, you go into your PS3's internet settings, and set the IP address (instead of automatic) to 192.168.7.199. It should connect, and should be that IP, and should be fine on the NAT.
Anyway, to expand on why uPnP, the purpose of it is to be able to have a system open whatever ports it needs automically on your router. This presents a huge security risk, and UPnP isn't authenticated. You can read more about it at
http://en.wikipedia.org/wiki/Universal_Plug_and_Play
Another option for those with more advanced routers, such as DD-WRT, is a static DNS lease based on mac address. It is located under the services tab, and you can input the mac address of your PS3 (Located in the network settings), and have your router automatically assign your ps3 to the IP that the ports are forwarded to, which allows you to keep your PS3 on automatic DNS settings.