I have IPv6. Why does my connection to the Windows Store fail?

I recently installed Windows 8, and I am unable to access the Store.

I receive the error:

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.

If I completely disable IPv6 on this computer, then I am able to access the Store normally.

How do I recover from this error?

There are no network proxies in use (it's at home!). "Use a proxy server" is not checked in the Internet settings. Other network connections work fine. I can browse the Internet from this PC with no issues and have no trouble accessing IPv6 web sites such as Google and Facebook. And the system time is in sync with "time.windows.com".

After a lengthy session with Sysinternals TCPView, I am observing the following behavior when opening Windows Store:

• When I first open it, the system opens an HTTPS connection to 157.55.145.242 port 443. This connection transfers some data and gets closed almost immediately. This appears to be a Microsoft IP address.
• Then, two connections are opened: an HTTPS connection to 23.12.49.138 port 443 and an HTTP connection to 2400:cb00:2048:1::adf5:3daf port 80. Neither of these two connections transfer more than a token amount of data, and remain open so long as the Store timeout screen (seen above) is up. I expected the Akamai IP address, since Microsoft is well known to use Akamai CDN, but I wasn't expecting to see a CloudFlare address! Both connections close as soon as I hit Alt+F4 to close Store.

Oh, and for those of you who didn't read it the first time, yes, the Internet works on this computer, on both IPv4 and IPv6. This occurs immediately after installation, before any anti-virus software has been configured. And Store is listed as an Allowed app in Windows Firewall, on both private and public networks.

This appears to be IPv6-related, since when I connect via IPv4 only, I can access the Store with no trouble.

Try if your store is working after EACH of the fixes below, until it's working

Make sure internet is working (duh)

Check if you can connect to websites. If you can't, try the following:

Press win + R and type inetcpl.cpl.
In the window that appears, click on LAN settings.
Check "Use Proxy Server for your LAN" is unchecked like this:

Check your date and time

Again, win + R and then type RunDll32.exe shell32.dll,Control_RunDLL timedate.cpl

Internet time -> Change settings -> Update now

Windows Services

win + R -> msconfig

Click on Diagnostic Start Up then reboot.

Use your Local Account or another Account

Try registering for a new one if you have just one.

Last resort: refresh

win + C -> Change PC settings -> General -> Refresh your PC

Source

This was eventually traced to an IPv6 routing issue with CloudFlare's network, and was affecting many other CloudFlare IPv6-enabled services as well. CloudFlare or its upstream providers have since resolved the issue.

(Though as of now they've screwed it up again...)