Here are my 2 cents.
I've been having this problem. Exact same situation as mzidx with only 2 users, and I'm an administrator.
I then signed up for Windows Insider Program and signed up for Windows to install every single available update. After restarting, absolutely nothing related to the Universal App would work at all. The Start menu would not pop up, Edge would not open, nothing. Other programs like Firefox and Internet Explorer would work, though.
I ultimately reinstalled Windows, and I'm getting the error again on a fresh new clean install.
I believe it has something to do with permissions for Windows to use its own utilities, but I hope someone can figure it out soon.