I had such a similar error when i was recently upgrading my play service dependency. It seems to occur when you leave out updating the firebase dependencies that correspond to the version of play services you use. I beleive this is the most recent update of these dependencies
Here is what the two versions of my dependencies were:
Error version of dependencies
compile 'com.google.firebase:firebase-appindexing:10.0.1'
compile 'com.google.android.gms:play-services-maps:10.0.1'
compile 'com.google.android.gms:play-services-places:10.0.1'
compile 'com.google.android.gms:play-services-location:10.0.1'
compile 'com.google.firebase:firebase-auth:9.8.0'
compile 'com.google.firebase:firebase-database:9.8.0'
compile 'com.firebaseui:firebase-ui-database:1.0.1'
compile 'com.google.firebase:firebase-storage:9.8.0'
Working version of dependencies
``
compile 'com.google.firebase:firebase-appindexing:10.0.1'
compile 'com.google.android.gms:play-services-maps:10.0.1'
compile 'com.google.android.gms:play-services-places:10.0.1'
compile 'com.google.android.gms:play-services-location:10.0.1'
compile 'com.google.firebase:firebase-auth:10.0.0'
compile 'com.google.firebase:firebase-database:10.0.0'
compile 'com.firebaseui:firebase-ui-database:1.0.1'
compile 'com.google.firebase:firebase-storage:10.0.0'
``
Google seems to move play service updates along with firebase updates these days. Hopes this saves a few souls out there.