How to solve Firebase API initialization failure (Android + Firebase)

Well, after struggle a lot I found what was causing my problem. Basically I had two libraries modules - that happened to be of my own - each one of them importing different versions of com.android.support:appcompat-v7.* and google play services. Made all of them import the same version and problem is gone.

I met the same error, solved by upgrade firebase-core:

dependencies {    
    compile 'com.google.firebase:firebase-core:9.0.2'
}