Xamarin - Android - Visual Studio - The application could not be started
Renamed Application name.
Added Package name.
App. started working on Emulator, Renamed application again, app. continued to run.
Note: Resetting device, un-installing the app. and related runtime etc. from settings did not work for me.
Hope this helps someone.
I solved the issue. Somehow the application still existed on my device even though it did not show up in my applications and I needed to remove it.
The solution was to find an old APK that I had emailed and I installed that. Then I uninstalled the application and deployed it again from Visual Studio. This time it worked.
You can read more here: https://forums.xamarin.com/discussion/8501/install-failed-update-incompatible
EDIT (March 13th, 2017):
Seems a lot of people found this answer useful so I decided I should update it with an alternate method to uninstall the app if you don't have access to an old version.
As Atul Chaudhary and Nestel mentioned, you can open up your adb command prompt and run adb uninstall <com.your.application.package.name>. If there are any remnants of your application which remain this should get rid of them.
Running this command from the adb shell solved it for me:
adb shell pm uninstall -k com.packagename
To access the adb shell from Visual Studio Tools -> Android -> Android Adb Command Prompt.
Very interesting error, seems like Visual Studio is unable to unistall the previous version completely.
Obviously the OP figured out the issue to their problem but I still wanted to post an answer relating to an issue I had with the same error message. I am using Visual Studio (within Parallels) and attempting to debug the app on a Xamarin Android Player instance (which is running on my Mac).
I kept getting this error and realized that a different, more helpful, error message was showing up in the Build Output saying that I was not supporting the correct architecture.
Heading into the Android Project Properties -> Android Options -> Advanced -> and checking x86 finally allowed my to successfully deploy to the Xamarin Android Player.