Problem: When you post a new build of the same solution to a new share, the VSTO object tries to reference the same installed package as the existing solution.
In my case, I had released a demo version of my application to users and now I was releasing the full application. Any user that had installed the demo would first have to uninstall the demo to run the current solution.
Fix:
Modify the solution Id in the VSTO project to a new GUID
