This happened to me after I changed the build variant to release and then hit the green play button and then attempted to upload the resultant apk from the auto-generated build folder.
Instead, after a clean/rebuild (which will erase that auto-generated build folder), make sure to use Build * Generate Signed APK (and check off signing for both v1 and v2). That will generate signed APKs in e.g. app/free/release. The Play Store should accept this APK. Also, go into the build folder and save the mappings from app/build/output so you can deobfuscate a stack trace from any errors that come up for your users.
(Not sure why Google doesn't save the mapping in the same folder tree as the signed APK...)