Windows 7 and 8.0 bug: Store: PC is not connected to Internet, try again later
The steps a windows machine uses to discover internet access are here:
How does Windows know whether it has internet access or if a Wi-Fi connection requires in-browser authentication?
Try doing those manually and see where you get stuck. In particular check that none of the magic URLs are blocked by a firewall or have erroneous entries in your hosts or hostslm file.