I've been having this issue for many months. I'm just now wanting to upgrade to Windows 8.1, but was never able to do so because the Store app (and several others) simply wouldn't open or function. Here's my winstore.log file:
2014-02-24 00:15:36.810, _Info_ WS [00002192:00001064] ***********************************************************************
2014-02-24 00:15:36.810, _Info_ WS [00002192:00001064] Process name: C:\Windows\System32\WWAHost.exe
2014-02-24 00:15:36.810, _Info_ WS [00002192:00001064] User name: BRIAN-PC\Brian
2014-02-24 00:15:36.811, _Info_ WS [00002192:00001064] Computer name: BRIAN-PC
2014-02-24 00:15:36.811, _Info_ WS [00002192:00001064] Windows build: 9200.16628.amd64fre.win8_gdr.130531-1504
2014-02-24 00:15:36.811, _Info_ WS [00002192:00001064] Client version: 670
2014-02-24 00:15:36.811, _Info_ WS [00002192:00001064] WinStoreUI QFE version: 1
2014-02-24 00:15:36.812, _Info_ WS [00002192:00001064] Switched to view state: FullScreenLandscape
2014-02-24 00:15:36.819, _Info_ WS [00002192:00001064] CNetworkState::_Initialize: NLM_CONNECTION_COST flags initalized to 0x00000001
2014-02-24 00:15:36.819, _Info_ WS [00002192:00001064] CNetworkState::_GetDataPlanStatus: MaxDownloadSize = -1, DataLimit = -1, Usage = -1
2014-02-24 00:15:36.821, _Info_ WS [00002192:00001112] ***********************************************************************
2014-02-24 00:15:36.821, _Info_ WS [00002192:00001112] Process name: C:\Windows\System32\WWAHost.exe
2014-02-24 00:15:36.822, _Info_ WS [00002192:00001112] User name: BRIAN-PC\Brian
2014-02-24 00:15:36.822, _Info_ WS [00002192:00001112] Computer name: BRIAN-PC
2014-02-24 00:15:36.822, _Info_ WS [00002192:00001112] Windows build: 9200.16628.amd64fre.win8_gdr.130531-1504
2014-02-24 00:15:36.822, _Info_ WS [00002192:00001112] Client version: 670
2014-02-24 00:15:36.822, _Info_ WS [00002192:00001112] WinStoreUI QFE version: 1
2014-02-24 00:15:36.825, _Info_ WS [00002192:00001064] Globals::InitializePhase1: user is NOT opted in to BI
2014-02-24 00:15:36.825, _Info_ WS [00002192:00001064] DiscoveryService::SetOSInfo(): Edition: edition, Type: type
2014-02-24 00:15:36.825, _Info_ WS [00002192:00001064] DiscoveryService::SetOSInfo(): Edition: ProfessionalWMC, Type: Retail
2014-02-24 00:15:36.825, _Info_ WS [00002192:00003116] WinStoreCache::DoQuery: Provider 1: Cache miss for GetOSEditionInfo.
2014-02-24 00:15:36.827, _Info_ WS [00002192:00001064] CWinStore::_BlockSuspend: 1
2014-02-24 00:15:36.829, _Info_ WS [00002192:00002356] WinStoreCache::DoQuery: Provider 0: Cache miss for DiscoveryService.
2014-02-24 00:15:36.829, _Info_ WS [00002192:00002700] WinStoreCache::DoQuery: Provider 3: Cache miss for DigitalMarker.
2014-02-24 00:15:36.829, _Info_ WS [00002192:00002356] CSQRProvider::GetData: Entering for selector DiscoveryService.
2014-02-24 00:15:36.829, _Info_ WS [00002192:00002700] CCommerceProvider::GetData: Entering for selector DigitalMarker.
2014-02-24 00:15:36.829, _Info_ WS [00002192:00002356] CHttpRequest::_CreateConnectionAndSendRequest: Server: go.microsoft.com, URL /fwlink/?LinkID=195324&clcid=0x409
2014-02-24 00:15:36.829, _Info_ WS [00002192:00006664] WinStoreCache::DoQuery: Provider 4: Cache miss for PrefetchParentalControls.
2014-02-24 00:15:36.830, _Info_ WS [00002192:00002356] CHttpConnectionCache::GetSession: New session handle 0x000000EE4E3DF670
2014-02-24 00:15:36.830, _Info_ WS [00002192:00002356] CHttpConnectionCache::OnNewConnection: Caching handle 0x4f027c40 for go.microsoft.com:443
2014-02-24 00:15:36.830, _Info_ WS [00002192:00002356] CHttpRequest::_CreateConnectionAndSendRequest: hRequest 0x4f01bdb0 is for GET /fwlink/?LinkID=195324&clcid=0x409
2014-02-24 00:15:36.831, _Info_ WS [00002192:00006664] WinStoreCache::DoQuery: Provider 4 returned 0 bytes (0x00000000) for PrefetchParentalControls
2014-02-24 00:15:36.833, _Warning_ WS [00002192:00002356] CHttpRequest::_GetProxyInfoForUrl: Autoproxy failed: 0x80072f94
2014-02-24 00:15:36.833, _Info_ WS [00002192:00002356] Proxy list = (null), Proxy bypass = (null), Proxy access type = 0
2014-02-24 00:15:36.833, _Info_ WS [00002192:00002356] CHttpRequest::_SendRequest: Calling WinHttpSendRequest, hRequest 0x4f01bdb0 attempt 1
2014-02-24 00:15:36.835, _Error_ WS [00002192:00006664] Request 0x4f01bdb0 failed, error 12007 for result 5
2014-02-24 00:15:36.835, _Info_ WS [00002192:00002356] CHttpRequest::_SendRequest: WinHttpSendRequest hRequest 0x4f01bdb0 (1) result: 0x80072ee7, proxy time: 0
2014-02-24 00:15:36.835, _Info_ WS [00002192:00002356] CHttpConnectionCache::CloseConnection: Closing handle 0x4f027c40 for go.microsoft.com:443
2014-02-24 00:15:36.835, _Error_ WS [00002192:00002356] CHttpRequest::FetchResource: _CreateConnectionAndSendRequest failed: 0x80072ee7
2014-02-24 00:15:36.835, _Info_ WS [00002192:00002356] CSQRProvider::GetData: Leaving for selector DiscoveryService with result code 0x80004005.
2014-02-24 00:15:36.835, _Warning_ WS [00002192:00002356] WinStoreCache::DoQuery: Provider 0 returned failure for DiscoveryService, hr=0x80004005
2014-02-24 00:15:36.855, _Info_ WS [00002192:00001064] CNoOpSink::OnEvent: hrEvent = 0x00000000
2014-02-24 00:15:36.855, _Info_ WS [00002192:00001064] CWinStore::_UnblockSuspend: 0
2014-02-24 00:15:36.855, _Error_ WS [00002192:00001064] CWinStore::_NavigateToErrorPage: 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 <a id='linkRefresh'>try again</a>.
2014-02-24 00:15:38.054, _Info_ WS [00002192:00003116] WinStoreCache::DoQuery: Provider 1 returned 648 bytes (0x49ea2b40) for GetOSEditionInfo
2014-02-24 00:15:38.058, _Info_ WS [00002192:00002720] WindowsStoreCache::DoCheckCacheDiskUsage: Disk usage is 0.000001 percent
2014-02-24 00:15:38.079, _Info_ WS [00002192:00002700] DebugHeader: GetData:
2014-02-24 00:15:38.079, _Info_ WS [00002192:00002700] WinStoreCache::DoQuery: Provider 3 returned 5218 bytes (0x4f080230) for DigitalMarker
2014-02-24 00:15:38.807, _Info_ WS [00002192:00001064] visibilityState changed to: hidden
I've tried just about every possible solution that people have been posting with no success. Maybe I'm just missing something somewhere?