@redsonic’s answer worked for me.. By simply moving apply plugin:
'com.google.gms.google-services' after the dependecies in
build.gradle (Module: app)

I’m using Android Studio 1.5.1 with Gradle version 2.10

In case you are using Gradle version older than 2.10 you’ll also need to update that by selecting the ProjectName or app directory in the Project tool Windows and pressing F4. This will open Project Structure window, select Project from the menu and update Gradle version to 2.10. Press OK (Android Studio will download it in background).

build.gradle (Project: ProjectName)

dependencies {
    classpath 'com.android.tools.build:gradle:1.5.0'
    classpath 'com.google.gms:google-services:2.0.0-alpha6'
}

build.gradle (Module: app)

dependencies {
    compile fileTree(dir: 'libs', include: ['*.jar'])
    compile 'com.google.android.gms:play-services:8.4.0'
}

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