Erro "Não foi possível instanciar atividade"

Um dos meus aplicativos Android tem cerca de 100.000 usuários e, cerca de 10 vezes por semana, recebo a seguinte exceção sendo relatada a mim por meio da ferramenta de mercado do Google:

java.lang.RuntimeException: Unable to instantiate activity ComponentInfo{org.rebm.asp/org.rebm.asp.MainActivity}:
  java.lang.ClassNotFoundException: org.rebm.asp.MainActivity in loader dalvik.system.PathClassLoader[/mnt/asec/org.rebm.asp-1/pkg.apk]
at android.app.ActivityThread.performLaunchActivity(ActivityThread.java:2659)
at android.app.ActivityThread.handleLaunchActivity(ActivityThread.java:2753)
at android.app.ActivityThread.access$2500(ActivityThread.java:129)
at android.app.ActivityThread$H.handleMessage(ActivityThread.java:2107)
at android.os.Handler.dispatchMessage(Handler.java:99)
at android.os.Looper.loop(Looper.java:143)
at android.app.ActivityThread.main(ActivityThread.java:4701)
at java.lang.reflect.Method.invokeNative(Native Method)
at java.lang.reflect.Method.invoke(Method.java:521)
at com.android.internal.os.ZygoteInit$MethodAndArgsCaller.run(ZygoteInit.java:868)
at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:626)
at dalvik.system.NativeStart.main(Native Method)
Caused by: java.lang.ClassNotFoundException: org.rebm.asp.MainActivity in loader dalvik.system.PathClassLoader[/mnt/asec/org.rebm.asp-1/pkg.apk]
at dalvik.system.PathClassLoader.findClass(PathClassLoader.java:243)
at java.lang.ClassLoader.loadClass(ClassLoader.java:573)
at java.lang.ClassLoader.loadClass(ClassLoader.java:532)
at android.app.Instrumentation.newActivity(Instrumentation.java:1021)
at android.app.ActivityThread.performLaunchActivity(ActivityThread.java:2651)
... 11 more

Na pesquisa on-line, esse erro geralmente indica que há algo errado com o arquivo de manifesto e os nomes dos pacotes que estão sendo usados. No entanto, não consigo reproduzir esse erro em meus próprios dispositivos ou no emulador. Eu só conheço esse erro através da ferramenta de mercado. Tudo o que posso concluir é que é um erro raro, porque sei que muitas pessoas estão usando o aplicativo e nenhuma das análises indica que ele trava.

Alguém sabe qual é o problema ou como posso diagnosticá-lo?