I followed the steps as mentioned above. However, i couldn't get the same options as described. BTW, I own a Moto E. In Settings, under Apps (Manager), I managed to find Google Play Services.
I clicked Clear Cache.
However, the problem persisted.
There were no such option as Uninstall or Uninstall updates. In Manage Space, I found Clear All Data. Yeah, i know it may sound extreme..but it isn't. No important data is actually deleted. Once it deletes the required data...it re-collates all necessary data.(You'll notice it in the sudden fall and rise in app memory - which happen immediately). After that, the error stopped. And Google apps like gmail, books etc. continue to work fine.
The ones with a similar interface, u could try this. Probably the equivalent to Uninstall Updates.