vijaydsk None of the above solved the problem. Even when I said that changing the DNS server from 8.8.8.8 to my router's IP did, it actually didn't (I figured it out later).
What really solved the problem for me was setting up dnsmasq because it caches DNS records.
Here's what I did:
1) Install dnsmasq (yum install dnsmasq)
2) Remove any DNS server entries from /etc/sysconfig/network-scripts/ifcfg-eth0
3) Add "dns=none" (without quotes) to /etc/NetworkManager/NetworkManager.conf (in the "[main]" section)
4) Add this entry to /etc/resolve.conf: nameserver 127.0.0.1 (if there's any line starting with "nameserver", remove it)
5) Add "server=8.8.8.8" and "server=8.8.4.4" (without quotes) to /etc/dnsmasq.conf (right below the comment "Add other name servers here[...]")
6) systemctl enable dnsmasq (so that it starts on boot)
After that, maybe you'll have to restart the network service or the server itself (if you can afford it), but I can't remember for sure.