Win10 Cortana failing with "Activation of app [...] CortanaUI failed with error: The remote procedure call failed"

Last week I upgraded from a clean Windows 8.1 Pro to Windows 10 Pro (64 bit). Immediately after the upgrade I did a Windows Reset to get the clean install feeling. Unfortunately my Start Menu is opening very slow (takes 2 full seconds), and Cortana isn't working. The search bar is in the task bar, but I cannot type in it or anything. I'm currently at build 10240.

After searching on the internet, I did attempt to re-register all packages:

Get-AppXPackage -AllUsers | Foreach {Add-AppxPackage -DisableDevelopmentMode -Register "$($_.InstallLocation)\AppXManifest.xml"}

Unfortunately, this did not help. Every time I open the Start Menu, two errors show up in the event log:

Faulting application name: SearchUI.exe, version: 10.0.10240.16384, time stamp: 0x559f3d35
Faulting module name: SearchUI.exe, version: 10.0.10240.16384, time stamp: 0x559f3d35
Exception code: 0xc000027b
Fault offset: 0x00000000001423c2
Faulting process id: 0x1468
Faulting application start time: 0x01d0d02f71fa36be
Faulting application path: C:\Windows\SystemApps\Microsoft.Windows.Cortana_cw5n1h2txyewy\SearchUI.exe
Faulting module path: C:\Windows\SystemApps\Microsoft.Windows.Cortana_cw5n1h2txyewy\SearchUI.exe
Report Id: 5de0ff92-30e9-4e39-a8b4-3798d067c3df
Faulting package full name: Microsoft.Windows.Cortana_1.4.8.152_neutral_neutral_cw5n1h2txyewy
Faulting package-relative application ID: CortanaUI

and

Activation of app Microsoft.Windows.Cortana_cw5n1h2txyewy!CortanaUI failed with error: The remote procedure call failed. See the Microsoft-Windows-TWinUI/Operational log for additional information.

The TWinUI log shows the following:

Activation of the app Microsoft.Windows.Cortana_cw5n1h2txyewy!CortanaUI for the Windows.Launch contract failed with error: The remote procedure call failed..

SearchUI.exe in the Cortana folder is V2, datestamp ‎Friday, ‎July ‎10, ‎2015 6:57:17 AM. File version 10.0.10240.16384 KB3081424 fails to install with error code 0x80070bc9. Any suggestions on where to search next to get Cortana working?

I had this problem also. To fix it I had to go to the folder:

C:\Users\%USERNAME%\AppData\Local\Temporary Internet Files\

right click, properties, security tab, add the group "all application packages" and give that group full control. once i did that i could get into all of my metro apps again.