0x80004005 error when launching Windows Store in Windows 8.1

I ran into a problem recently that really had me scratching my head for awhile:  when I launched the Windows Store on Windows 8.1 with a new user, the store itself failed with an error.  The error message in the Store app read, "We weren't able to connect to the Store.  This might have happened because of a server problem or the network connection timed out.  Please wait a few minutes and try again.  (0x80004005)."

The annoying thing about this (besides it not working) was that it pretty clearly wasn't trying to access the store:  the app itself was failing before even having the chance to time out.

This error persisted through reboots, and it only affected a new user.  Creating another new user (local or MS account) had the same effect:  the store errored out.  New apps that attempted to install as part of a sync from another computer too, would fail in installing.



I tried some of the easy-to-find solutions (they might work for you):

1. wsreset.exe
2. a Powershell script 
3. Deleting the user and creating a new one
4. switching over to a local (or MS) account
5. rebooting
6. running sfc /scannow (in an admin cmd prompt)

None of these would get the store to work.

I ran procmon and looked for access denied and other errors.  I couldn't find a thing.

Finally, out of desperation, I tried the Windows Update troubleshooter.  I used the built-in troubleshooting control panel rather than the downloadable app.

This seemed like a long shot, as Windows update worked just fine.  So did the store, for that matter, from other computer accounts.

The troubleshooter reported that it found two problems, and it fixed them.  When I switched back to the new account, the store worked.  Magic.  

I don't know at all where the problem might have been, but perhaps this will help you, as well.