I appreciate, I really do, that this question is nearly a year old! However I had the exact same issue, and it appears this is the only reference to this exact problem on the internet!
What was posted here didn't solve my issue, however it did point me in the direction of ProGuard. Since I have solved it, I wanted to post it so future people (perhaps me again) do not end up shouting at the monitor "Tertium, What did you see!" #xkcd.
Turns out I didn't have Proguard set up correctly. After much trial and error I found the following lines let me carry on:
-keep class com.google.** { *; }
-dontwarn com.google.**
To add a bit of background context:
- I am building via Maven, android-maven-plugin
- It is a LibGDX based game
This may not be the most optimal solution, but it was one that got me out of a hole.