I had the same problem with s:3.
Here's how I fixed it for me (this morning)
Remove all google accounts.
Go to Settings -> apps -> Download manager and clear data
Settings -> apps -> Play Store...clear data
Settings -> apps -> Google service Framework...clear data
Reboot
Settings -> Add...