Occasionally, I have problems with a ClassNotFoundException being thrown after deploying a new version of my app to my Android devices. These usually occur when I update some of the 3rd party libraries I’m using. After SDK 17 libraries should go into a ‘libs’ directory instead of the ‘lib’ directory. This has occured a couple times using various SDK versions. I tried numerous solutions like ‘clean’ and installing a fresh copy of the apk but none of that worked. What did work, was removing the project from Eclipse (Indigo) and re-adding existing projects from source. It looks like the project gets corrupted from the IDE and a re-add helps to solve this problem.
Maybe this will be fixed in SDK 20? I hope so.