"You have configured a new VPC with a private subnet and added a NAT Gateway and configured the subnet route table to route all internet traffic via the NAT Gateway. However when you try to run a yum update, none of your instances are able to reach the internet. What could be the problem?"
I read this as there is only a private subnet where the NAT Gateway has been put into. That will never work because NAT Gateways should be in public subnets (subnets attached to IGW). Please enhance this question a bit so it reflects the actual situation.
I’ll take a look at the question and see if it needs a clarification,