Delete your debug certificate under ~/.android/debug.keystore on Linux and Mac OS X; the directory is something like %USERPROFILE%/.androidon Windows.

The Eclipse plugin should then generate a new certificate when you next try to build a debug package. You may need to clean and then build to generate the certificate.

Primarily for older phones

I only encountered the App not installed error when trying to install an apk on my phone which runs on 4.4.2 aka KitKat, but my friend did not encounter this error on his phone which runs on 6+. I tried the other solutions such as removing the old/debug version of the app because the apk was a release version, clearing the debug app's data, and even clearing all of my cached data. Then, finally I realized all I had to do was select both signature versions when building my signed apk.

Before I only had V2 (Full APK Signature) selected, but after selecting V1 Jar Signature as well, I was able to successfully install my signed APK on my 4.4.2 device. Hope this helps others!