Android recommends using ProGuard to obfuscate the APKs. However, sometimes ProGuard ends up obfuscating something the app needs, thus causing crashes with exceptions as ClassNotFoundException, NoClassDefFound and such. I ran into this issue recently while releasing the Baby Monitor app.
As suggested here, adding -keep to the progcfg.txt file works. The trick to figure out which classes to keep from obfuscating. If your app implements a Service, make sure that the interfaces are not obfuscated. To do this, add the following line to progcfg.txt:
-keep public interface * extends android.os.IInterface