Steve, I think I got it fixed. It might be a missing dependency of some sorts. I restored all the Windows crap I previously uninstalled by running the following Powershell (as an admin):
Get-AppXPackage -AllUsers | Foreach {Add-AppxPackage -DisableDevelopmentMode -Register "$($_.InstallLocation)\AppXManifest.xml"}
Perhaps I removed something I shouldn't have. You can give it a go, or try it on a machine with a fresh Windows install.
Good luck,
Mark