I came across this a lot and what always fixed it for me was the following (I am not sure what the proper order was, to be honest):
1) Go to system > apps > all
2) Go to Google Play Store and delete cache and data
3) Go to Google Services Framework and delete data
Reboot.