I experienced the very same issue but the problem was not my Security Group or NACL.
Background:
I added a domain name via Route53.
The domain name continues to be hosted with DiscountASP.net.
The VPC was created manually (no wizard or default).
I created a DHCP Option Set with my domain name and the 4 servers IP addresses given to me by Route53.
Analysis:
First, I needed to prove that the problem was not the Security Group or the NACL.
I did this by attatching the default DHCP Option Set to my new VPC. It worked!
I could do the yum update and "curl http://www.google.com". No problem.
I then created a new DHCP Option Set using my domain name and the Google DNS Servers.
8.8.8.8 & 8.8.4.4
This also worked.
I then took 1 of the 4 DNS Servers IPs provided by Route 53 and used it with my domain name in a new DHCP Option Set.
I ran a test and it failed. I repeated the same test with 2 of the remaining 4 DNS Servers IPs, creating two separate DHCP Option Sets.
I ran tests and they both failed.
After checking the spelling of my domain name I could only conclude that the problem was the domain name servers.
Solution:
Amazon Virtual Private Cloud User Guide (PDF page 222)
Amazon DNS Server (Sub topic)
"When you create a VPC, we automatically create a set of DHCP options and associate them with the VPC. This set includes two options: domain-name-servers = AmazonProvidedDNS, and domain-name=domainname-for-your-region. AmazonProvidedDNS is an Amazon DNS server, and this option enables DNS
for instances that need to communicate over the VPC's Internet gateway. The string AmazonProvidedDNS maps to a DNS server running on a reserved IP address at the base of the VPC IPv4 network range, plus two. For example, the DNS Server on a 10.0.0.0/16 network is located at 10.0.0.2."
From page 221:
DHCP: domain-name-servers
Option Name Description
"The IP addresses of up to four domain name servers, or AmazonProvidedDNS. The default DHCP option set specifies AmazonProvidedDNS. If specifying more than one domain name server, separate them with commas."
The IP addresses that its referring to are for external domain name servers (excluding the possibility you have created a custom DNS).
So I created my final DHCP Option Set using my domain name and domain-name-servers=AmazonProvidedDNS. It worked!
By the way the VPC DNS Resolution = yes & DNS Hostname = no.