Adding on late in case someone else stumbles across this as I did: AppLocker can break the Start menu and Cortana. I attempted to follow w32sh's answer, and got the following error message:
Add-AppxPackage : Deployment failed with HRESULT: 0x80073D01, The package deployment operation is blocked by policy.
Please contact your system administrator. (Exception from HRESULT: 0x80073D01)
error 0x800704EC: Deployment of package
Microsoft.Windows.ShellExperienceHost_10.0.15063.674_neutral_neutral_cw5n1h2txyewy was blocked by AppLocker.
When I enabled AppLocker I had it create default rules and autocreate rules based on what was on the system, but apparently that wasn't sufficient. Perhaps an update broke it.
Regardless, the fix for me was to change the enforcement to "Audit" mode. Be aware that this disables the protections you get from AppLocker. And it's tricky since the damned start menu is broken. You can get around this by using Windows-X and clicking the Console or Powershell (depending on your setup) with Admin Priveleges. Then run secpol.msc and follow the instructions
at Configure an AppLocker Policy for Audit Only in the section To audit rule collections by using the Local Security Policy snap-in
In case that site ever goes away, here are the rather quick steps:
- Click Start, type secpol.msc in the Search programs and files box, and then press ENTER.
- If the User Account Control dialog box appears, confirm that the action it displays is what you want, and then click Yes.
- In the console tree, double-click Application Control Policies, right-click AppLocker, and then click Properties.
- On the Enforcement tab, select the Configured check box for the rule collection that you want to enforce, and then verify that Audit
only is selected in the list for that rule collection.
- Repeat step 4 to configure the enforcement setting to Audit only for additional rule collections.
- Click OK.