Boa tarde.
Tive o mesmo problema q vc, e foi dificil resolver, mas consegui com muito custo. É o seguinte, provavelmente vc usa um model ADSL e um roteador, o problema de NAT3 é que vc está em uma rede interna de um servidor DHCP do roteador e do modem, ai fica impossível se conectar a outros jogadores, você poderá navegar normalmente e fazer downloads mas não pode se conectar a outros PS3.
Primeiro conecta o PS3 direto no modem ADSL via cabo para ver como fica o status da conexão, pra ver se muda o NAT. Se continuar NAT3 o problema está no modem, ai vc vai ter q configurar seu modem no modo bridgi (não lembro como escreve) e colocar para o roteador fazer o login do usuário PPPoE (o nome de usuário e senha que vc usa do seu servidor, para autenticação de ADSL, exemplo Terra, UOL, Globo). Feito isso ligue o PS3 pelo roteador novamente e veja como está a configuração. Caso continue como NAT3 vc terá que liberar as portas do roteador, porém tem um jeito mais fácil de fazer isso, vá na opção DMZ do roteador e digite o IP do PS3 (lógico q pra isso vc tem que definir um IP manualmente no PS3 para que fique statico), feito isso, reinicie o video game, roteador e modem, e tente novamente. aqui funcionou ai não sei mas pode dar certo.
Caso ligue no modem ADSL e o NAT mude para 1 ou 2 o problema está no roteador, ai fazendo isso que te expliquei de digitar o IP do PS3 na configuração DMz do roteador deve resolver, pelo menos pelo que li em vários forums.
Se a medição de velocidade no teste de rede não funcionar e parecer uma mensagem informando q seu roteador não suporta fragmentos de IP ai vc vai ter que fazer mais um processo de configuração do PS3 está a alguns posts acima nesta mesma págia, eu quem postei uma solução.
Demorei um dia intero pra conseguir resolver isso pegando várias dicas diferentes e alguns foruns até conseguir montar um esquema que funcionace aqui.... ufaa
mas valeu muito o esforço
Acabei de achar esse turorial, o melhor q já vi:
http://forum.outerspace.terra.com.br/showthread.php?t=244781
http://forum.outerspace.com.br/showthread.php?t=137684
Aguardo retorno.