AWS EC2 Network problem

Based on what you have described, this is very likely a routing issue between your NAT Gateway, your subnets, and your route tables. Here are the things to check, in order of how often they cause this exact problem.

1. Check that your NAT Gateway is in a public subnet, not a private one This is the most common cause. A NAT Gateway must be deployed in a subnet that has a route to an Internet Gateway. If you placed the NAT Gateway in one of your private subnets, it cannot reach the internet itself, so it cannot forward traffic for your instances. To verify: go to VPC > NAT Gateways, note which subnet it is in, then go to VPC > Route Tables and check the route table associated with that subnet. It must have a route with destination 0.0.0.0/0 and target igw- followed by your Internet Gateway ID (your Internet Gateway).
2. Check that your private subnet route tables point to the NAT Gateway, not the IGW Your three private subnets each need a route table with 0.0.0.0/0 pointing to nat- followed by your NAT Gateway ID (your NAT Gateway). If they point to the IGW directly, that will not work because your instances do not have public IP addresses. To verify: go to VPC > Subnets, select each of your three private subnets, and check the Route Table tab. Confirm the 0.0.0.0/0 route target is your NAT Gateway.
3. Check that the route table is actually associated with your subnets A common mistake is editing a route table that is not the one your subnets are using. AWS has a "Main" route table, but if your subnets are explicitly associated with a different one, your edits to the Main table will have no effect. Under VPC > Subnets, check each subnet's Route Table tab to confirm it is the table you modified.
4. Check that your NAT Gateway has an Elastic IP and shows status "Available" Go to VPC > NAT Gateways. Confirm the status is "Available" (not "Failed" or "Pending") and that it has an Elastic IP address assigned.
5. Check your Network ACLs (NACLs), not just security groups You mentioned changing security groups, but NACLs are a separate layer that applies at the subnet level. Unlike security groups, NACLs are stateless, so you need rules in both directions. Go to VPC > Network ACLs and check the NACLs for your private subnets and the NAT Gateway's subnet. Verify that outbound traffic on ports 80 and 443 is allowed, and inbound traffic on ephemeral ports (1024-65535) is allowed for return traffic. The default NACL allows everything, but custom NACLs may not.
6. Check VPC DNS settings Go to VPC, select your VPC, and confirm that both DNS resolution and DNS hostnames are enabled. If DNS is disabled, your instances cannot resolve hostnames like package repositories, which produces "network is unreachable" errors. The correct setup should be: Internet Gateway attached to your VPC NAT Gateway in a public subnet (with a route to the IGW) and an Elastic IP Private subnet route tables: 0.0.0.0/0 > NAT Gateway Public subnet route table: 0.0.0.0/0 > Internet Gateway NACLs allowing traffic in both directions VPC DNS enabled If you can share which of these checks passed or failed, I can help narrow it down further.

Based on your description, you've taken several correct steps, but there are a few additional areas to verify for your EC2 instances in private subnets to access the internet:

Route Table Configuration: Verify that your private subnet route tables have a route entry that directs internet-bound traffic (0.0.0.0/0) specifically to the NAT gateway, not the internet gateway. The internet gateway should only be associated with your public subnet where the NAT gateway resides.

NAT Gateway Placement: Ensure your NAT gateway is deployed in a public subnet (not the private subnets where your instances are). The public subnet must have its own route table with a 0.0.0.0/0 route pointing to the internet gateway.

Network ACL Rules: Beyond security groups, check your network ACLs. The network ACLs for your private subnets must allow outbound traffic to the internet and allow inbound return traffic. Similarly, the NAT gateway's subnet network ACL must allow inbound traffic from your instances and outbound traffic to internet hosts, plus the corresponding return traffic.

NAT Gateway Status: Confirm that your NAT gateway is in the "Available" state and functioning properly.

Instance Network Configuration: Check the operating system network configuration on your instances. Verify that the primary network interface is configured to start at boot and that there are no hardcoded IP addresses or MAC addresses that could interfere with proper DHCP configuration.

Protocol Restrictions: Ensure your instances are only using TCP, UDP, or ICMP protocols, as NAT gateways support only these protocols.

You can use VPC Reachability Analyzer to create a path analysis between your instance and the internet gateway to identify where the connectivity is breaking down. Additionally, enabling VPC Flow Logs can help diagnose if connections are being dropped due to security group or network ACL rules.
Sources
Troubleshoot network configuration issues in EC2 Linux instance | AWS re:Post
Use tools to troubleshoot Amazon VPC network conenctivity | AWS re:Post
Troubleshoot EC2 instance internet access with a NAT gateway | AWS re:Post