How was the new APK compiled? Was the underlying app version incremented beyond just the SOTI Package? Was the same signing processed followed for the new app build? If you don't sign it with the same certificate and increment the app version then Android won't let you apply an update over the top and you will get those errors when SOTI goes to apply the package. 

I am not 100% sure but I believe it would be incremented and also probably signed with a different certificate. It's a third party app we install via SOTI, so we have no control over how it's compiled. It's a whole new version number. So in this case my best bet is to do a install script that removes the existing install, and then installs the newer one? Permissions will be lost but if that is the only way to do it, we'll figure something out. Isn't there a way to manually apply permissions in a post-install script or does Android not allow that in this case? Thanks!

If the signing process changed between app versions then that is likely the cause of your issues. There also could be a conflict with Google Play Protect if there is an app compatibility with your devices or GPP has detected a vulnerability of some kind. 

By having a pre-install script that removes any prior versions will solve your problems but will clear out any app cache and reset any permissions that have been prompted. Depending on the permission, and if you're using AE for management, you should be able to silently grant them with a post-install script.  Here is a sample of how that would look:

afw_set_permission_grant_state PACKAGE NAME android.permission.WRITE_EXTERNAL_STORAGE allow

afw_set_permission_grant_state PACKAGE NAME android.permission.READ_EXTERNAL_STORAGE allow

Ok thank you, that is helpful. I did try a command to turn of Google play protect and that didn't help... only other thing is we still use the Android+ management method (OS 7.1), so do the post-install permission methods work for that one?