Amazon VPC NAT not working

I'm trying to create a NAT instance for my VPC to allow instances on private subnets connect to the internet (most importantly, S3). I tried following the instructions here: http://docs.amazonwebservices.com/AmazonVPC/2011-07-15/UserGuide/index.html?VPC_NAT_Instance.html . Unfortunately, the instances in the private subnet (call it 10.10.2.0/24) cannot reach the internet.

I have done the following:

1. Create a NAT instance (Amazon's ami-vpc-nat-1.0.0-beta.i386-ebs (ami-d8699bb1)) in public subnet (call it 10.10.1.0/24).


2. Changed "Source / Dest Check" to disabled.


3. Created a new entry in the default routing table (which is used by 10.10.2.0/24) and had it point to the ID of the newly created instance.



4. Associated an Elastic IP address with the NAT instance.


5. Allowed all outbound traffic on the security group of the NAT instance.


6. Ensured that all traffic could pass between the two subnets.

I've tried also doing this with an existing instance using iptables, but had no luck. And I have verified that sys.net.ipv4.ip_forward is 1, just in case anyone was wondering. And I still have no internet connectivity from the instances on 10.10.2.0/24. Does anyone have any suggestions?