I'm have connectivity issues with the Google Play Store app. I have a non-rooted Note 3 (4.3). The had worked the first few weeks I had the phone in December and then hasn't worked since. I get the same "No connection - Retry" error everytime I access it. I've been have trouble with Google Play Services since I tried disabling it when I realized how much battery life it drained. I've had trouble using Youtube at times but never as persistent and consistent as the Play Store.
I have done the following:
Wi-fi/LTE connections, no difference between the two
Airplane mode on/off
Manual and automatic date/time
Updated both Google Play Services and Google Play Store via Android Police
I have basically done everything except a factory reset which seems like the next logical step but it does not fix the problem for everyone. I am trying to figure out if there is anything else I haven't tried that I may be overlooking.