In my case, the target phone had the app already installed, but in a "disabled" state. So the user thought it was already uninstalled, but it wasn't. I went to the main app list, clicked on the "disabled" app, uninstalled it, and then the APK would go on.