None of the above solution worked for me. Not sure if it is specific to my setup or new release.
I am using Android Studio Beta 0.8.9 and I was not getting any com.google.android.gms:play-service in the library list on following this instruction:
Go to File -> Project Structure -> Select Project Settings -> Select 'Dependencies' Tab Click '+' -> 1.Library Dependencies -> Select com.google.android.gms:play-services:+
I had already done this:
First of all you have to launch the sdk manager and download and install the following files located under "extras": Android support repository, Google play services, Google repository.
What resolved it was to add from SDK Manager, "Google play services for Froyo" then repeating the first step.
Did not understand the reason properly but this worked.
PS: I just observed that even now when I search for play-services this does not come, but when I directly scroll and look through the list it is right there.