PlayStation defines NAT as three different types:
Type 1: Connected directly to the Internet.
Type 2: Connected to the Internet via a router.
Type 3: Connected to the Internet via a router.
According to Official PlayStation documentation (located here). Type 3 connections may not be able to communicate with other PS3 systems, as well as use voice / video chat communication features.
Over the years we have discovered commonalities with home network settings that, when addressed, have fixed certain connection problems related to NAT. Many of these issues can be easily fixed by adjusting your router/console settings.
Make sure your NAT is type 1 or 2.
Make sure UPnP is set to available.
Make sure the following ports are forwarded:
TCP Ports: 80, 443, 5223, and UDP Ports: 3478, 3479, and 3658