This error is usually caused by the WiFi/Data connection you're using. Try to switch between them and then go to Settings > Applications manager > All> Google Play Store & Google Play Service. Tap on them and force close, clear data and clear cache, then reboot the phone. It's the most common way to fix this error and it actually works.
Additionally, boot the phone into recovery mode (Volume Up + Power + Home button) and select Wipe Data/Factory Reset. This also fixes most of the common errors.