UPnP is supposed to help remedy the situation as well, if your router supports it. I think that setting will dynamically open and close ports for you based on what your application needs, but maybe I'm wrong on that. I've personally never been able to enable UPnP and it fix my console NAT problems, but that's always the first thing that's recommended.
Also, since you're on the PS3, remember that both a Type 1 and Type 2 NAT are supposed to be OK. Type 3 is the strict. These types can be found by doing a quick network test from the XMB.