I suggest that you reboot your device and then try again. If that doesn't work, you should set the Google DNSs.
Primary DNS: 18.104.22.168
Secondary DNS: 22.214.171.124
To do this if you are connected to a wifi simply long-press the wifi name in the settings, click on modify, tick the advanced box and change the DNS servers.
If you are connected using mobile data, you can use setDNS (you will have to download it from the internet without the play store).
I hope I helped!