I was having the same problem and the same log messages. I haven't gotten to the root cause, but at least in my case I was able to fix it by updating the "Google Play services" app.

You can update this app at https://play.google.com/store/apps/details?id=com.google.android.gms.

I hope this fixes the problem for others who are experiencing similar issues.