Could not find com.google.android.gms:play-services:3.1.59 3.2.25 4.0.30 4.1.32 4.2.40 4.2.42 4.3.23 4.4.52 5.0.77 5.0.89 5.2.08 6.1.11 6.1.71 6.5.87

Question

Check if you also installed the "Google Repository". If not, you also have to install the "Google Repository" in your SDK Manager.

Also be aware that there might be 2 SDK installations - one coming from AndroidStudio and one you might have installed. Better consolidate this to one installation - this is a common pitfall - that you have it installed in one installation but it fails when you build with the other installation.

Just install Google Repository form your sdk manager and than restart Android Studio.

In addition to installing the repository and the SDK packages one should be aware that the version number changes periodically. A simple solution at this point is to replace the specific version number with a plus (+) symbol.

compile 'com.google.android.gms:play-services:+'

Google instructions indicate that one should be sure to upgrade the version numbers, however adding the plus deals with the changes in versioning. Also note that when building in Android Studio a message will appear in the status line when a new version is available.

One can view the available versions of play services by drilling down on the correct repository path:

References

This site also has instructions for Eclipse, and other IDE's.

I've been strugglin with this problem for hours till found this post. Just like @ligi said, some people have two SDK folders (Android Studio, which is bundled and Eclipse). The problem is that it doesn't matter if you downloaded the Google Play Services library on both SDK folders, your ANDROID_HOME enviroment variable must be pointing to the SDK folder used by the Android Studio.

SDK Folder A  (Used on Eclipse)
SDK Folder B  (Used on AS)

ANDROID_HOME=<path to SDK Folder B>

After change the path of this variable the error was gone.

I had the same problem because I had:

compile 'com.google.android.gms:play-services:5.2.8'

and I solved changing the version numbers for a '+'. so the lines has to be:

compile 'com.google.android.gms:play-services:+'

Adding this as a second reference because I had a similar problem..
I had to explicitly add '.aar' as a registered file type under the 'Archives' category in AS settings.

If you already have Google Repository installed, make sure it's updated. I had to update my Google Repository and services. This was after I updated Android Studio.