Ok. I'm having similar issues to a couple of ppl who have posted in this thread.

I'm using a Netgear DG834PN wireless AP/router. UPnP is enabled on the AP, but my PS3 is detecting it as disabled. Consequently, I'm getting NAT3.

UPnP is working for my PCs that are connected to the AP, so it's got to be something specific to the PS3. Any ideas?

On the PS3, the wireless connection is extremely slow compared to a wired connection. Sometimes, it just won't connect at all when it's wireless, but wired never has an issue.