Internet access from private VPC subnet?

yes, you must have iptables masquerading set up on the nat host.

iptables -A POSTROUTING -t nat -s (private-subnet/cidr) -j MASQUERADE

we have the same set up, you've done everything else correctly (disable source check, point private subnet to the interface of the nat instance, point public subnet to the igw).

Just stumbled across this having a similar problem. Assuming you used the wizard to create the NAT instance, the masquerade rule mentioned above would already be there - this is only something you need to add if you're going to "roll your own" NAT instance. (I usually do that so I can double-up on this and also make it an OpenSWAN L2TP/IPSec remote user VPN server).

What I had forgotten to add since the last time I created one of these, were rules which allow all traffic (or at least what you want to allow) from all private security groups or subnets which will route traffic via the NAT instance. The NAT instance will not accept such outbound traffic without rules to allow it - don't just think about what's coming in from the Internet to get to it. Not sure if that's your issue, as you did mention adding 22/80/443 to your NAT security group, but thought I'd suggest this for others who might have a similar problem.

I battled with this for a while, until I found this:

Then, launch an instance into your public subnet from an AMI that's been configured to run as a NAT instance. Amazon provides Amazon Linux AMIs that are configured to run as NAT instances. These AMIs include the string amzn-ami-vpc-nat in their names, so you can search for them in the Amazon EC2 console.

http://docs.aws.amazon.com/AmazonVPC/latest/UserGuide/VPC_NAT_Instance.html#NATInstance

I had set up the NAT server as my own standard (Ubuntu) instance, once I used the Amazon Linux AMI and updated my routing tables it started working.