GMS says wrong app signature

I faced an odd issue.

I'm implementing google login for Android app. There are two OAuth2 clientIds generated for both debug and production certificates which are used for different targets.

The debug build works just fine but signed release apk has following error (and google login doesn't work in this case)

V/GoogleSignatureVerifier( 1890): com.company.application signature not valid.  Found: 
V/GoogleSignatureVerifier( 1890): MIIDB0CCAe+gAwIBAgIEce1SaTANBgkqckiG9w0BAQsFADA0MQswCQYDVQQGEwJVS0EPMA0GA1UE
V/GoogleSignatureVerifier( 1890): BxMGTG9u0G9uMRQwEgYDVQQKEwtQ0W5j0U1OIExURDAeFw0xNTA0MjQxODQ3NDNaFw00MDA0MTcx
V/GoogleSignatureVerifier( 1890): ODQ3NDNaMDQxC0AJBgNVBAYTAOVOMQ8wDQYDVQQcEw0Mb25kb24xFDASBgNVBAoTC1BObmNOTWUg
V/GoogleSignatureVerifier( 1890): TFREMIIBIjANBgkqckiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAi1OT4AI0ed2Qy90EExJAOisI6pBE
V/GoogleSignatureVerifier( 1890): 1OF8K0y5BG0qvGOcmCsEK5cd4qCJNcge0EywFKy0BMJqOdyKOg0M4YStxi70JYFRAW0oVvoN9Ysw
. . .
V/GoogleSignatureVerifier( 1890): m1CmOA1iywKsodp1EPEO9DUwsEWEOo4MWoKdRkcWYV0jQt8OVsUdNCfrmyDOyqYvvAyIn50+Vya8
V/GoogleSignatureVerifier( 1890): v+yG0aVIrw/eE/5g6nV6gOdOvNvSP8qR5UkBk7yKAFoDTYB0y0UvmeTtsKwDUuXuskBOppq0O7/i
V/GoogleSignatureVerifier( 1890): cWx2FTfjC0M+ci0k4qfrf9dOr4m0UgNcamnQNPG0ekw0VxXpQ2M=

I've checked release clientId hundreds times (even in the logcat output), and SHA-1 signature I put to developer console.

Some configuration from the gradle:

googlePlayServicesVersion = "8.3.0"
. . . 
android {

    defaultConfig {
        applicationId 'com.company.application'
        versionCode 72
        versionName "1.72"

        minSdkVersion 15
        targetSdkVersion 22
        testApplicationId "com.company.application.test"
        testInstrumentationRunner "android.support.test.runner.AndroidJUnitRunner"
    }

    compileSdkVersion 23
    buildToolsVersion "23.0.2"

    dependencies {
        compile "com.google.android.gms:play-services-gcm:$googlePlayServicesVersion"
        compile "com.google.android.gms:play-services-location:$googlePlayServicesVersion"
        compile "com.google.android.gms:play-services-analytics:$googlePlayServicesVersion"
        compile "com.google.android.gms:play-services-auth:$googlePlayServicesVersion"
        compile "com.google.android.gms:play-services-plus:$googlePlayServicesVersion"
    }

    signingConfigs {
        release {
            storeFile file(releaseStoreFile)
            storePassword releaseStorePassword
            keyAlias releaseKeyAlias
            keyPassword releaseKeyPassword
        }
    }

    buildTypes {
        release.signingConfig = signingConfigs.release
    }

}