CONNECTION ERROR - (Merged Threads )

Having the same problem. I've done all the steps you listed and even tried uninstalling the Google Play service / Google Store and having both of the services update back from factory settings. No luck...

It may be a Google Play thing as I'm unable to log into PoGo either.

*UPDATE: Still not working after phone factory reset...