Clearing user data for Google Play Services

From experience ;

You won't face any grave troubles or troubles for that matter -worst case being you may be required to log in again into Google accounts. But this isn't going to fix your storage problem as it gets recreated

But don't delete Google Services Framework data. Your Google based apps will stop working and you may need to install apps all over again or do a factory reset / flash ROM again ( this was the option I chose when things turned troublesome )

Thanks to Izzy for additional inputs on Google Services Framework

Google engineer explains why you shouldn’t clear Google Services Framework data | TalkAndroid.com. That would essentially reset the ANDROID_ID assigned to the device, so a lot of apps will feel like "factory reset". Especially those using GCM might behave strangely then (need to re-register with the corresponding servers as the ID changed)

ANDROID_ID is set on first start and usually lives until you do a factory-reset; details can be found in my (Izzy's) article Android Identifiers: How Android devices and their users are identified.