Thread is a bit old, but I got this error too.
My problem was that I used two different
com.google.android.gms:play-services Versions in my gradle file.
compile 'com.google.android.gms:play-services-gcm:7.5.0'
compile 'com.google.android.gms:play-services-analytics:7.3.0' // WRONG!
Make sure, that you always use same versions like:
compile 'com.google.android.gms:play-services-gcm:7.5.0'
compile 'com.google.android.gms:play-services-analytics:7.5.0'