Instances within the private subnet are unable to access the internet using NAT gateway.

Based on the configuration you've described, there are a few potential issues that could be preventing your instances in the private subnet from accessing the internet through the NAT gateway:

1. Internet Gateway: Ensure that your VPC has an Internet Gateway attached to it. The NAT gateway requires an Internet Gateway to function properly. Without it, the NAT gateway cannot route traffic to the internet.

2. NAT Gateway Configuration: Verify that your NAT gateway is properly configured and in an "Available" state. Check the Amazon VPC console under the NAT Gateways section to confirm its status and ensure it has an associated Elastic IP address.

3. Public Subnet Route Table: Make sure the route table associated with your public subnet (where the NAT gateway is located) has a route for 0.0.0.0/0 pointing to the Internet Gateway. This is crucial for the NAT gateway to have internet connectivity.

4. Elastic IP Association: Confirm that the NAT gateway has an Elastic IP address associated with it. This is required for the NAT gateway to function correctly.

5. VPC DNS Settings: Check that DNS hostnames and DNS resolution are enabled for your VPC. These settings are necessary for proper name resolution.

6. Instance Configuration: Ensure that the instances in your private subnet are configured to use the VPC's DNS server. This is typically done automatically, but it's worth verifying.

7. Security Groups and Network ACLs: Although you mentioned checking these, double-check that both inbound and outbound rules are correctly configured. Sometimes, overlooked rules can cause connectivity issues.

8. NAT Gateway Capacity: If you're running a large number of instances or generating a high volume of traffic, you might be hitting the NAT gateway's connection limits. Consider creating additional NAT gateways if this is the case.

If you've verified all these points and are still experiencing issues, you may want to use VPC flow logs to analyze the traffic patterns and identify where the communication is breaking down. Additionally, checking the CloudWatch metrics for your NAT gateway can provide insights into its performance and any potential issues.
Sources
NAT gateways - Amazon Virtual Private Cloud
Troubleshoot NAT gateways - Amazon Virtual Private Cloud
Add a NAT Gateway to an Existing VPC - Amazon AppStream 2.0

NACL is stateless. You should check the Inbound Rules for Subnet NACL as well.