Я получал похожую ошибку, когда пытался использовать одну и ту же версию для всего:
implementation 'com.google.android.gms:play-services-base:16.0.0'
implementation 'com.google.android.gms:play-services-analytics:16.0.0'
implementation 'com.google.android.gms:play-services-awareness:16.0.0'
implementation 'com.google.android.gms:play-services-cast:16.0.0'
implementation 'com.google.android.gms:play-services-gcm:16.0.0'
implementation 'com.google.android.gms:play-services-location:16.0.0'
implementation 'com.google.firebase:firebase-messaging:16.0.0'
Проблема была исправлена для меня, когда я сделал следующее:
1)Использована последняя доступная версия каждой службы:
implementation 'com.google.android.gms:play-services-base:16.1.0'
implementation 'com.google.android.gms:play-services-analytics:16.0.8'
implementation 'com.google.android.gms:play-services-awareness:16.0.0'
implementation 'com.google.android.gms:play-services-cast:16.2.0'
implementation 'com.google.android.gms:play-services-gcm:16.1.0'
implementation 'com.google.android.gms:play-services-location:16.0.0'
implementation 'com.google.firebase:firebase-messaging:17.6.0'
2) Обновлена Android Studio до последней версии, доступной сегодня (Android Studio 3.4).
3) Обновлена версия Android Gradle Plugin до 3.4.0 и версия Gradle до 5.1.1.