I had this problem after updating ADT.
I was storing all of my JAR files in a folder called "lib" and adding the jars to the build path the normal Eclipse way. This worked fine until my update.
After my update, I was getting the NoClassDefFoundError for a class that I could clearly see was included in the jar (checking out the ReferencedLibraries classes).
The solution was to remove my jars from the build path and rename my "lib" folder to "libs". This is an ant convention, and seems to be the way the new ADT finds and includes libraries in an .apk file. Once I did this, everything worked fine.