I fixed this by not signing the app first and not with Maven. I added this to my build path.
<plugin>
<groupId>com.jayway.maven.plugins.android.generation2</groupId>
<artifactId>android-maven-plugin</artifactId>
<inherited>true</inherited>
<configuration>
<sign>
<debug>false</debug>
</sign>
</configuration>
</plugin>
After that I signed my app by hand: jarsigner -verbose -sigalg MD5withRSA -digestalg SHA1 -keystore /home/myself/.android/release.keystore myapp-1.0.apk androidreleasekey