I tried a local admin account and a local account, all the same though...
Have you disabled UAC? Netplwiz.exe
Never mind. I just saw the same thing. I suspect it is a misleading message, e.g. just conveniently using one which would be appropriate in another scenario. Probably the real problem is that there are bits and pieces which are needed to be running which are being suppressed by safe mode.
Sorry for the bad suggestion.
It would be nice though if we could tell whether there was even an attempt to contact the Store or whether this is just more hocus pocus. E.g. that way we would know if there is really connectivity or if something else is broken. Even nicer if it would tell us exactly what is broken. E.g. in this case which specific piece isn't running.