To reproduce:

• Open attached Unity project
• adb install Empty.apk attached to this ticket (you can do it, by opening logcat package, tools->open terminal->adb install <path_to_emty.apk>
• In SampleScene->MainCamera, change Background color to something else, for ex., Red
• Build & Run from Unity to Android device (it will attempt to install the package with the same name, but different key)
• Nothing will start on the device and there's no error in Console, if it will start, the background color will not be Red, meaning the old package was used
• That's the issue, fastdeploy fails to install the app and doesn't report any errors

Actual Result: The app is not installed and no error is printed

Expected Result: The is not installed, error is printed to console with the reason why it wasn't installed "Unable to install APK to device. "

Note: If you'll attempt  to do normal adb install with apk produced by editor you'll get
{code:java}
E:\Projects\unityv5\External\NonRedistributable\Android sdk\builds\platform-tools>adb install D:\UnityProjects\Empty\a.apk
Performing Streamed Install
adb: failed to install D:\UnityProjects\Empty\a.apk: Failure [INSTALL_FAILED_UPDATE_INCOMPATIBLE: Package com.DefaultCompany.Empty signatures do not match previously installed version; ignoring!]
{code}
Workaround: uninstall the app from the device after changing the keystore / key or building from the different computer than before.

There's a ticket on Google's issue tracker - [https://partnerissuetracker.corp.google.com/u/1/issues/236615033,] where they said:

"After discussions internally we can acknowledge that this functionality is currently not working as expected. However we have no timeline for any remedy to this situation and in the meantime advise Unity not to use this functionality."