I had similar problems after changing my google password on my S4. I followed these steps and it worked for me too:
First I uninstalled the updates for the Google Play store and then uninstalled the updates for Google play services. Now everything seems fine.
To uninstall the updates, go to...