USB接続して実機でデバッグできていたアプリをアンインストールした後、リリースビルドしたapkをWebページからダウンロードしてインストールしようとすると「アプリはインストールされていません。」と表示されてインストールできないという問題が発生しました。
環境はNexus 5、Android 5.1.1 Lollipopです。
同僚に、既に同じ名前のパッケージが存在する場合にこのエラーが出ると教えてもらいました。設定→アプリを確認したところ、アンインストールしたと思っていたアプリが「このユーザーでは未インストール」という表示で残っていました。
アプリの詳細を開き、メニューから「すべてのユーザーからアンインストール」を実行するとアンインストールされ、無事にAPKをインストールできるようになりました。
考察
Android 5.0からスマホでも使えるようになったマルチユーザー機能で、ゲストユーザーが有効になっていました。
Playストアからダウンロードしたアプリはユーザーごとにインストールされますが、USB接続（adb）経由でインストールしたアプリはすべてのユーザーにインストールされるそうです。このため、ホームアプリのすべてのアプリから普通にアンインストールしただけでは、インストールされたままになってしまうようです。
参考：Android 4.2で追加になったマルチユーザーについて、 気になっていた点を色々と調べてみたのでメモ。 ■Android…
他の情報
最初にハマって調べたところ、JDK 7で署名がうまくできていない場合に発生するという情報がありましたが、今回は無関係でした。
ちなみにJDK 8 + Android Studio 1.2.2の環境で、GUIのBuild→Generate Signed APKから問題なくリリースビルドのAPKを生成できています。