Also something to note (thanks @Raymond Lee):
If you happen to be using an Android Studio / Gradle Version 2.2, your application will automatically be signed with both the v2 and v1 schemes. This may be why you are running into this issue.
https://developer.android.com/about/versions/nougat/android-7.0.html#apk_signature_v2
Updating to version 2.3+ will give you the option to choose your signature version:
https://stackoverflow.com/questions/43525209/android-studio-can-not-choose-signature-version
- Justin
2 People are following this question.