I'm using Visual Studio 2013 SP2, and am having the same issue.
Regularly, I will create a new release of our Excel Addin by Rebuilding the solution in VS, signing it, deploying it, but it is uninstallable.

If I then quit Visual Studio, then run Visual Studio again, Rebuild and Redeploy, then it'll work without any problems. Which is fine... but, of course, it means each time I deploy, I need to check that the damn thing will install okay !
It's worrying that VS continues to build installables which quietly contain this issue.
There are plenty of articles mentioning this bug, errr, issue (some from 8 years ago !!), suggesting I need to "rebuild my manifest file", but why doesn't this happen automatically when a do Rebuild in Visual Studio..?
ClickOnce Deployment Issue
ClickOnce Deployment Error