While updating the last of my devices to Windows 8.1, I received the following message when accessing the Windows Store. 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. I attempted to perform the tasks (as referenced below) but none worked for me, so in line with my last post on accessing the internet, here's a few alternatives to the many out there on connecting to the store.

1. Choose Settings on the Charms menu
2. Choose Change PC settings "In Your account the following may be displayed"

If it requires account verification, click verify to enter current password

If verification is not displayed, choose Disconnect.

Note: Be sure to backup your recovery key before switching to a local account

3. After backing up your recovery key, choose skip backup.
4. Enter Current password and select Next

You'll be asked to create a local account, enter the following:

User name

Password

Reenter password

Password hint

5. Select Next
6. Select Sign out and finish

Your computer will prepare and sign out, sign in with the information you entered in the local account.

7. Go back to Accounts and select Connect to a Microsoft account under Your account. It would ask you to Sign in to your Microsoft account, Click Next.

You may have to enter a code to verify identity, ensure your phone number and/or email is correct on your Microsoft account profile

8. Select Next on SkyDrive

9. Select Switch to switch to a Microsoft account from a local

 References:

http://gshaw0.wordpress.com/2013/08/22/fixing-the-windows-8-1-we-werent-able-to-connect-the-store-error/

http://helpdeskgeek.com/windows-8/fix-windows-8-we-werent-able-to-connect-to-the-store-error/

http://answers.microsoft.com/en-us/windows/forum/windows_8-windows_store/

Update 01/07/2014: For those who are having problems check this KB if it applies to you http://support.microsoft.com/kb/2787623/EN-US leave a comment to reach out to me.