There is a question here about this already (though,short of re-installing Windows, which I'm obviously trying to avoid, the other solutions don't work for me), but I have some research to add, and a possible solution... which I don't understand, but perhaps someone here is able to shed light on how to implement it? I'm using Visual Studio 2015 Community on Windows 10 Pro x-64 with Anniversary Update (and latest cumulative update).
There is a possible work-around - details at https://social.technet.microsoft.com/Forums/windows/en-US/2f51398c-cef2-4686-9505-904d3f71ef6d/windows-10-applocker-packaged-app-white-list-blocks-store?forum=win10itprogeneral - where the resolution is to allow all Windows App Store apps, however no steps are given, so I don't know how to do that.
There is a relevant hot fix at https://support.microsoft.com/en-gb/kb/2719305, however that is targetting an older version of Windows, so I'm not sure of the repercussions of trying that. I'm leaving that as my last resort short of re-installing.
And finally, there is re-installing, as per the other thread on here, as the Anniversary Update is considered the suspect (and I'm past the rollback window). I already had the AU when I first tried UWP, so I never had it working to begin with to know if this is the culprit or not. I have never touched applocker myself (had never heard of it) - I have this problem out of the box.
Apart from the time involved, I don't want to re-install as there has been mixed success with it - for one person it fixed it, for another it fixed it initially but the problem came back. I am trying to get a permanent fix (and only re-install if I can't find one).
Anyone know a permanent fix for this? Or how to implement the first suggestion? Or implications of the second?
P.S. for the sake of completeness (and to pre-emptively answer this question), one of the things I already tried is the MS trouble-shooter for this issue (I think I found this one on MSDN from memory). It suggested using my MS login instead of my local user, and to change the temp environment variables back to default (I had them pointing to RAMdisk), but doing those things failed to fix the issue.
Well, I ended up re-installing Windows, having corrupted it along the way, and that ended up fixing the issue. I found along the way that the problem actually stops ALL apps from the store installing (I never did find out how to implement the store fix I mentioned in my question), and that provides a quick way to see if the problem is fixed (rather than trying to build/deploy your UWP app each time you think you've fixed it, just try installing a store app).
I did find something that MAY be a solution, at https://answers.microsoft.com/en-us/windows/forum/windows_8-winapps/this-app-wasnt-installed-error-0x80073cf9/92ec7c44-51ef-4c6a-9331-22958e01b4ec?page=1, which relates to how to recover from a corrupted user profile (I'm not being allowed to upload a snapshot of the relevant reply due to still being relatively new here. Sigh) - which I now believe to have been the cause - however I didn't get to try it out as I'd already corrupted Windows at that point. Note that none of the other solutions in that thread worked for me, so I would start with this one first, as the other solutions only worked for some people. If you have this problem then I would try that first before re-installing.
P.S. at one point it looked like the Anniversary Update may have caused the problem, however after I re-installed I tried before applying the AU, and then again with the AU, and it kept working afterwards,so that was NOT the culprit. It was the user profile/Windows being corrupt.