Android 7 users can't update my app, get error -504

Question

As the title states my android 7 users can't get the latest update of my app.

Note this is error -504

My app was built with API 22. I tried to build it with 23 and 24, get the same error with every build. It does work if I deploy app straight to phone, but not when I publish.

There are couple of posts with this problem and none of them seem to have definitive solution. I changed every possible thing I can and with no results.

1. Changed every API level and build tools
2. Tried different play services
3. Added applicationId to gradle
4. Enabled multidex

EDIT: This is what I get when trying to adb install:

Failed to install signed.apk: Failure [INSTALL_PARSE_FAILED_NO_CERTIFICATES: Failed to collect certificates from /data/app/vmdl2066131695.tmp/base.apk: META-INF/CERT.SF indicates /data/app/vmdl2066131695.tmp/base.apk is signed using APK Signature Scheme v2, but no such signature was found. Signature stripped?]

I'll add all the posts I have found for this error:

• Android Users Can't Install App From Play Store: Error -504 - No solution
  • Google Play Error code "-504" - can be caused when downgrading play services
  • Android app cannot update from market, after shareduserid added - after adding or changing shareUserId
  • My newly released app can't be installed: Error code: -504 - Build tools 23.0.2 was broken

My dependencies:

    compile 'com.android.support:multidex:1.0.1'
compile files('src/main/libs/javax.inject-1.jar')
compile files('src/main/libs/junit-4.11.jar')
compile files('src/main/libs/hamcrest-core-1.3.jar')
compile files('src/main/libs/GeoLib.jar')
compile files('src/main/libs/GeoPolygons.jar')
compile 'com.nostra13.universalimageloader:universal-image-loader:1.9.5'
compile files('src/main/libs/javax.annotation-3.2-b06-sources.jar')
compile ('uk.co.chrisjenx:calligraphy:2.1.0') {
    exclude group: 'com.android.support'
}
compile('com.google.android.gms:play-services:8.+') {
    exclude group: 'com.android.support'
}
compile('com.android.support:appcompat-v7:24.2.1') {
    exclude group: 'com.android.support'
}
compile('com.android.support:support-v4:24.2.1') {
    exclude group: 'com.android.support', module: 'support-annotations'
}
compile('com.android.support:palette-v7:24.2.1') {
    exclude group: 'com.android.support'
}
compile files('src/main/libs/FlurryAnalytics-6.1.0.jar')
androidTestCompile('com.android.support.test:runner:0.4.1') {
    exclude group: 'com.android.support', module: 'support-annotations'
}
androidTestCompile('com.android.support.test:rules:0.4.1') {
    exclude group: 'com.android.support', module: 'support-annotations'
}
androidTestCompile('com.android.support.test.espresso:espresso-core:2.2.1') {
    exclude group: 'com.android.support', module: 'support-annotations'
}
androidTestCompile('com.android.support.test.espresso:espresso-intents:2.2.1') {
    exclude group: 'com.android.support', module: 'support-annotations'
}
androidTestCompile('com.android.support.test.espresso:espresso-web:2.2.1') {
    exclude group: 'com.android.support', module: 'support-annotations'
}
debugCompile 'com.squareup.leakcanary:leakcanary-android:1.3.1' // or 1.4-beta1
releaseCompile 'com.squareup.leakcanary:leakcanary-android-no-op:1.3.1' // or 1.4-beta1
testCompile 'com.squareup.leakcanary:leakcanary-android-no-op:1.3.1' // or 1.4-beta1
testCompile 'junit:junit:4.11'
testCompile('org.mockito:mockito-core:1.9.5') {
    exclude group: 'org.hamcrest'
}
compile 'com.squareup:otto:1.3.5'
compile 'com.android.support:support-annotations:24.2.1'
compile 'com.google.code.findbugs:jsr305:2.0.1'
compile 'com.nineoldandroids:library:2.4.0'
compile 'pl.charmas.android:android-reactive-location:0.4@aar'
compile 'io.reactivex:rxjava:1.0.3'
compile 'com.github.castorflex.smoothprogressbar:library:1.1.0'
compile 'org.mod4j.org.apache.commons:lang:2.1.0'
compile 'com.android.support:support-v4:24.2.1'

Answer 1

For future reference I managed to fix this. Problem was with new signing system. I did manual signing and aligning. Before you could sign your app and then zipalign it. It will fail for new Android version. Signing should be the last thing.