Play Store error: "Check your connection and try again", tried all possible solutions I am using Huawei Honor 3C running v4.4.2, and is rooted for like 1 year without any issue. All of a sudden I am receiving this error: "Check your connection and try again" on Play Store.

Every time I connect to internet it gives me "Unfortunately, Google Play Services has stopped" error 1-2 times and then it goes away.

Possible solutions I already tried:


Changing time to/from Automatic/Manual
Removing 'hosts' file
Airplane mode On/Off 
Force stopping and clearing data/cache of Play Store and Google Play Services app
Uninstalling updates
Removing and adding the Google account again
Changing DNS to Google's or Open DNS' DNS in WIFI setting
Setting 'No Proxy' in Wi-Fi setting
Changing IP Address (incrementing)
Resetting all apps settings to default


On Device: 


Hangout and other apps are working fine
Using latest version of Google Play Store and Google Play Services
I am unable to find Service Framework app
I saw that you've all required steps but just check if Google Service Framework is deactivated - normally in the end of the app list or in a tab called "Deactivated" (Settings>Apps>All). Google Framework Services is a must to have in android so that you can update the apps and make connections with Google Servers.

Also reset app preferences (Settings>APPS>(Phone Menu) Reset App Defaults)