I've had the same issue for about 2 days now. I have both a Note 3 and a Nexus 7 (2013). I actually have 2 gmail accounts and find that the issue is only occurring with one of my gmail accounts. The issue occurs with my primary gmail account. When the issue first occurred, I could access all shops except the music shop in the Playstore on this account. I would get the Connection Timed Out message only for the Music store. Now I get the Connection Timed Out when I attempt to open the Playstore app and cannot go to any of the stores. I can go to My Apps and see what I have installed or available to Install (because it's on the other device).
Originally all the simple suggestions worked, cache cleared.. worked..not anymore..Force Stop the app..worked..not anymore....reset device...worked...not anymore...
I even thought I discovered the answer which involved removing the gmail account from one of my devices, leaving on only one of them and opening the app store..WORKED!! but not anymore...
I think it's odd that I can open that app with the nonprimary gmail account...so I'm not sure if the app is gone bad or if our gmail accounts are somehow affected. I sent in a ticket to gmail support yesterday and a guy named Zach did reply. He told me it was because I didn't have any payment setup in the Google Wallet. Well I updated that information because indeed my credit card information had recently changed, but I'm still having the same connection issue.. I'm not sure why my credit card information would stop me from "connecting" if anything, I'd think it would stop me from "purchasing"...
I'll send him a link from this forum to show him that Google seems to have an issue and it's, not just me thankfully...
Hopefully we get an answer soon...if I get one, I'll be sure to post it here...