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

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.