I know this might sound like a stupid question, but it has founding I don't have time to explain now. Do you have any updates pending install over reboot? Try rebooting anyway?
I wouldn't think so, my Surface was actually just rebooted this morning I believe. Nonetheless i'll try again and post back the outcome. :)
Since you are trying to help me troubleshoot by the looks of it, I'm assuming that this is my own problem and that you can access the Windows store, so I guess I will start with the troubleshooting instead of just waiting for a bit lol.
edit: A reboot didn't show that I was configuring any updates before shutdown and on startup... However, for some reason the store is available again.