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.