Unityでデバッグビルドをテストした後リリースビルドをインストールしようとすると「アプリはインストールされていません」と出てインストール出来ない

※Unity2019.2.1f1を使用しています。

デバッグビルドで実機テストを繰り返した後、リリースビルドでAPKを出力(USBデバッグではない)してサーバ経由でインストールしようとした所、「アプリはインストールされていません」と出てインストール出来ませんでした。

Play Storeのプロテクトが原因という回答もありましたが、解除しても解決しませんでした。結局、アプリを一度アンインストールしてから再度APKからインストールすると上手くいきました。
デバッグビルドとリリースビルドとでは色々と扱いが違っていて、差し替え(?)が上手く行かないのでしょうか？