I've followed Amazon's steps and list what I've done. I've created 6 subnets (4 private SN1: 10.50.1.0/24, SN2: 10.50.2.0/24, SN3: 10.50.3.0/24, SN4: 10.50.4.0/24) and 2 public (SN5: 10.50.101.0/24 and SN6: 10.50.102.0/24)

-I have a Bastion host and a NAT instance on SN5 and assigned EIP's to both. I created a test instance on SN1.

edit: -NAT instance has source/destination check disabled

-On the NAT instance, I had enabled the following commands to be bootstrapped:

echo 1 > /proc/sys/net/ipv4/ip_forward
iptables -t nat -A POSTROUTING -s 10.0.0.0/16 -j MASQUERADE

-In my VPC, the private subnets have their own route table and configured 0.0.0.0/0 to the NAT instance with 4 subnets being associated with the route table. I have a second route table for my public subnets and 0.0.0.0/16 is pointed towards the IGW (with the other 2 subnets associated with it).

-For Security Groups, I have the NAT instance accepting all traffic on each of the 4 subnets and all OUTBOUND traffic is allowed. For my test server, I have allowed all outbound access and have allowed all traffic from the public subnet of the NAT host.

I can ping internally with no issues. On my test instance, if I try to ping google.com, DNS resolves however I don't get a reply back. On my NAT instance, I run a tcpdump and can see the request being requested to google.com but it's not sending the reply back. My NAT host can ping and receive a reply from google. From the test host, when I ping the NAT instance, the tcpdump shows a request and receive.

Is there something I'm missing?

EDIT: I've figured it out - I had to save the iptable config and restart the service.