I also had the same problem. In starting, it was working fine then, but sometime later I uninstalled my application completely from my device (I was running it on my mobile) and ran it again, and it shows me the same error.
I had all lib and resources included as it was working, but still I was getting this error so I removed all references and lib from my project build, updated google service play to revision 10, uninstalled application completely from the device and then again added all resources and libs and ran it and it started working again.
One thing to note here is while running I am still seeing this error message in my LogCat, but on my device it is working fine now.