Colin Phillips (Alumni)
This morning I was getting this error message (in the title), both before and after rebooting, so I figured something was up. After looking online, I found this article from MS http://answers.microsoft.com/en-us/windows/forum/windows_8-windows_store/app-store-your-pc-isnt-connected-to-the-internet/97487893-5825-4b93-a413-9920696166db which describes that you can run a command line tool as follows.
c:> wsreset.exe
This resets the Windows Store App Cache and suddenly the store started working for me again. It even told me in the store app that the cache has been reset, and it was ready to go again. 
Yay!