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.