This might sound like an obvious thing to do but...

I have created a slightly modified production APK as hundreds time before. But this time I did not install the APK. I was happy enough with the debug version and the change was really small. However I have changed some libraries and it caused the DEX builder to mess up something. The production APK was crashing with java.lang.ClassNotFoundException in dalvik.system.BaseDexClassLoader.findClass. Awesome - I just wasted great opportunity to get some new players during Christmas and probably lost some of the regular players too.

Moral of the story: Always unistall the debug APK, clean your project, build it from scratch and install the production APK before uploading it to the play store using adb -install myapp.apk.