I'm also facing the same problem...
I had it working about 2 weeks ago (had to format, and now i am quite upset), following Chetna answer in here:
Google Play services out of date. Requires 3159100 but found 3158130
I tried to downgrade Google play services, replacing rev. 10 for 9 (rev. 9 was the version i had installed the time i got it to work - found it here: http://venomvendor.blogspot.co.il/2012/03/android-sdk-extras-by-google-inc.html), but, still no answers how to make it work! Don't understand why this question was down rated...
EDIT: So, after trying for almost a day to do this, i solved my problem (and maybe yours). There are a couple of steps to take care of this:
1) Follow Chetna answer in here (2nd answer):
Google Play services out of date. Requires 3159100 but found 3158130 (2nd answers), the gms and vending files are the most up to date that i know of.
If you don't understand what to do in step 1 =>
1.1) Go to the link above and download com.android.vending-20130716.apk and com.google.android.gms-20130716.apk.
1.2) Go to android\sdk\platform-tools and place those two files in the folder
1.3) Create AVD with android 4.2.2 (or version below) without google api and start it, then wait for it to load, till there is nothing more to load...
1.4) I only have windows so i only use this method: open command window (cmd) in that folder and do:
adb install com.android.vending-20130716.apk
and
adb install com.google.android.gms-20130716.apk
Both of these commands will take some time, and reply with a success or failure message (both replys must be success).
1.5) Turn off the AVD.
2) Just for the sake of it, downgrade your google play services to rev 9 (to do this uninstall from sdk or delete android\sdk\extras\google\google_play_services folder http://www.mediafire.com/download/bqs2kmza5vn8e04/google_play_services_9.7z - link from the venomvendor.blogspot)
3) Import android\sdk\extras\google\google_play_services\libproject\google-play-services_lib and copy it to your workspace, add it to your project through properties > add (in the library "menu")
4) Go to project > clean > clean all projects (this one did the trick for me)
It worked for me, hope it works for you too!
Cheers