I had the same problem with my nexus 5 as well but after downloading the new update and installing the play store it was completely resolved.
what i deed was.
1. Clear the Cache on your Android Device
2. Check Date / Time Settings
3. Either search latest playstore apk in google or download it...