Updated July 2014

We're seeing an increasing trend of the following error displaying upon logon to many of our client's computers running Windows 8.0  Oddly this seems to be happening more on Windows 8 "Core" (what you receive on a consumer system), versus Windows 8 Pro or Enterprise in the corporate environment. 

Windows couldn't connect to the windows all-user install agent service. Please consult your system administrator.

An investigation points to what appears to be some pretty buggy code in this particular service, which handles the installation of AppX (Metro/Tile World/Windows Store) applications. Somehow this service is crashing, and then further getting set to a Disabled state.

Most often, this problem will prevent standard (non-administrator) users from successfully logging on to the computer, or running certain Modern Apps or even Desktop software.

To fix this issue, you must be able to logon as an account that is in the Local Administrators group.  Once logged on as an Admin, resolving the issue is relatively simple. 

Open a Command Prompt As Administrator (this can be done from the Start Screen by searching for CMD, and then right click on the Command Prompt tile and choose Run as Administrator from the App Bar).  Then, execute the following three commands:

sc config AllUserInstallAgent start=demand
net start AllUserInstallAgent
sfc /scannow

The first two commands change the startup type of the required problem service, and the third will check for other corrupt file issues in your Windows installation.  It will take a good while to complete.  When all of the above are finished (whether fully successful or not), you must then instruct Windows 8 to do a FULL shutdown, as on most new computers it performs a hybrid shutdown by default which will not reinitialise all the necessary components.  Again, from the same Administrative Command Prompt type:

shutdown /s /f /t 5 

Turn your computer back on after its shut down fully and the errors should be resolved.  Still no word on an official fix from Microsoft yet.

Also of note, this only seems to affect original Windows 8, and not Windows 8.1.  In fact, this service has been removed completely on Windows 8.1.