Kept getting the same error message on Play Store (previously have uninstalled updates on Google Play Store and Google Play Services) after trying the steps in: Keep getting "Error retrieving information from server. [RH-01]" from the play store. Guess this is an instance not caused by corrupt cache. Thought of reversing the previous uninstallation of updates by installing the latest Google Play Store and Play Services. First proceeded with installation of latest Google Play Store apk but the same error message persisted. I then uninstalled the Google Play Store updates and installed the latest Google Play Services app and viola, Google Play Store auto-updated to the latest version and the error message was gone!
Therefore installing the latest Google Play Services app solved my problem. I googled for the latest Google Play Services app and downloaded online.