FirebaseUI authenticate with Google not working

Question

I'm using FirebaseUI for Android and both "Sign in With Facebook" and "Sign in with Email" methods are working fine, but "Sign in with Google" doesn't work. When I tap it it asks me to choose an account, I choose my gmail account, it shows a loading spinner for a second and then goes back to the sign in screen again like nothing happened.

Looking at the logcat logs I can see:

07-19 20:21:40.660 3345-12614/? V/BaseAuthAsyncOperation: access token request successful
07-19 20:21:40.661 3345-12614/? V/AuthAccountOperation: id token is requested.
07-19 20:21:40.777 20330-20330/? W/InstanceID/Rpc: Found 10013
07-19 20:21:40.889 3345-12614/? E/TokenRequestor: You have wrong OAuth2 related configurations, please check. Detailed error: INVALID_AUDIENCE
07-19 20:21:40.890 3345-12614/? D/AuthAccountOperation: id token request failed.

I have seen this post and made sure that Google sign in method is enabled on my Firebase project and that I have added the correct SHA-1 keys (tried it with both debug and release key).

This is the my build.gradle:

apply plugin: 'com.android.application'

android {
    signingConfigs {
        signing {
            ...
        }

    }
    compileSdkVersion 23
    buildToolsVersion "23.0.1"
    defaultConfig {
        applicationId "com..."
        minSdkVersion 19
        targetSdkVersion 23
        versionCode 1
        versionName "1.0"
        signingConfig signingConfigs.signing
    }
    buildTypes {
        release {
            minifyEnabled false
            proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.pro'
            signingConfig signingConfigs.signing
        }
        debug {
            signingConfig signingConfigs.signing
        }
    }
    productFlavors {
    }

    packagingOptions {
        exclude 'META-INF/LICENSE'
        exclude 'META-INF/LICENSE-FIREBASE.txt'
        exclude 'META-INF/NOTICE'
    }
}

dependencies {
    compile fileTree(include: ['*.jar'], dir: 'libs')
    testCompile 'junit:junit:4.12'
    // Module dependency on ParseUI libraries sources
    compile 'com.android.support:appcompat-v7:23.2.1'
    compile 'com.android.support:design:23.2.1'
    compile 'com.android.support:preference-v7:23.2.1'
    compile 'com.google.android.gms:play-services-maps:9.2.0'
    compile 'com.google.android.gms:play-services-location:9.2.0'
    compile 'com.google.android.gms:play-services-places:9.2.0'
    compile 'com.android.support:support-v4:23.2.1'
    compile 'com.android.support:support-annotations:23.2.1'
    compile 'com.squareup.picasso:picasso:2.5.2'
    compile 'com.android.support:recyclerview-v7:23.2.1'
    compile 'com.android.support:cardview-v7:23.2.1'
    compile 'com.google.maps.android:android-maps-utils:0.3.4'

    //Firebase
    compile 'com.google.firebase:firebase-core:9.2.0'
    compile 'com.google.firebase:firebase-database:9.2.0'
    compile 'com.google.firebase:firebase-auth:9.2.0'
    compile 'com.google.firebase:firebase-crash:9.2.0'
    compile 'com.firebaseui:firebase-ui-auth:0.4.2'

    //Geofire
    compile 'com.firebase:firebase-client-android:2.5.0+' // Remove this once geofire updates to 1.2 to support firebase 3.0
    compile 'com.firebase:geofire:1.1.0'

    compile 'com.github.lsjwzh.RecyclerViewPager:lib:v1.1.0-beta5'
    compile 'com.squareup.okhttp3:okhttp:3.4.0-RC1'
}

apply plugin: 'com.google.gms.google-services'

This is how I'm starting the AuthUI

startActivityForResult(
                    AuthUI.getInstance()
                            .createSignInIntentBuilder()
                            .setLogo(R.drawable.logo)
                            .setProviders(
                                    AuthUI.EMAIL_PROVIDER,
                                    AuthUI.GOOGLE_PROVIDER,
                                    AuthUI.FACEBOOK_PROVIDER)
                            .build(),
                    RC_SIGN_IN);