For People that are experiencing a similar problem, where you get an error message saying something like:
"We weren't able to connect to the Store. This might have happened
because of a server problem or the network....blah blah blah"
And the above methods will not work, here is the solution:
1.) Go to Settings
2.) Then Change PC Settings
3.) Then Your Account
4.) Then you should see a little link to the right that says
Verify Your Identity
5.) Click that link, and type in your password that you use to login to your pc.
6.) Go to Task Manager to close the Store
Hope this helps!
I experienced this when using the 8.1 beta, when the beta expired and I tried to download the newest version of Windows I ran into this problem and searched, and searched, and searched.....and found many solutions like the ones above, until I finally came across a blog that described the above method.