Uninstall playstore, google play services and wipe theirs data,reboot and let it update itself than try again.
No need to download manually they will be updated automatically.
Remove them again,reboot and open playstore,wait maybe 5 minutes and they will get updated.
did you greenify playstore/services? coz this error happened to me before. After de-greenifying them, back to normal.
I didn't uninstall updates, I uninstalled the app itself, and yes I'm rooted. When you said uninstall playstore, I had that option only, so should I do a factory reset? Why is it not working when I downloaded a new version?
Sent from my LG-D802 using Tapatalk
In the op you said new and stock phone,i thought you are not rooted.
Here is the playstore http://d-h.st/M5s
And this is play services https://play.google.com/store/apps/...ium=organic&utm_term=google+play+services+apk