This might save some people from losing a few hours over a seemingly simple issue. When you update the Google Play Services SDK, and possibly the Android API, it might happen that your application suddenly crashes when calling isGooglePlayServicesAvailable with a NoClassDefFoundError.
What is weird of course is that the application compiles and builds normally, and it worked before. So you rebuild, remove the Google play services from your project, add it again, following all the steps meticulously. But the application keeps crashing with the same error.
The solution is easy, but impossible to guess from the error given in eclipse. To fix it you need to upgrade the Android SDK Build-tools. Go to the Android SDK Manager and select the highest version of the build-tools (currently 20). Deselect the old build-tools just in case. Install packages, delete packages, and restart eclipse. Clean your projects and deploy. It should work now.
mflerackers 
I honestly love you more than life itself right now!!!!!!!!!!!!!!!!!!!!!!!! I spent 3 days trying to figure out what the hell was wrong with this and you solved my problem in 2 minutes!!!!!!!! THANK YOU SOOOOOOOOOOO MUCH!!!!!!
Thank you so much… it really worked.
I would like to add that it will be needed to increment the VM values in eclipse.ini
Please use this as reference:
http://stackoverflow.com/questions/9471194/unable-to-execute-dex-gc-overhead-limit-exceeded