clearing data can cause other problems, namely, the infamous 'could not be downloaded due to an error AEC:0 RPC:5' and then all your Gapps stop working (can't sync Gmail, Books, Music, etc).
the only solution is then removing and readding your Google account to the device. i found that one out the hard way on my Nexus 10 when i tried the clear data for everything like Framework and Play Store attempting to get the Android 4.3 update before it was officially released. it didn't work and caused me headaches fixing all the issues that i caused by doing that. if Play isn't working the problem is at Google's end, and not yours. just wait it out.
Whenever Play 'Plays' up, i first try using Amazon Apps or side-load from my Dropbox backup APKs. if that fails, i use 1Mobile Market as a final resort if the app i am trying to use is free. it won't have any paid apps so if you paid for things from Google Play, you're sunk unless you backed up the APK file (root only) after install or you learn to live without it until it gets fixed. i wished i had backed up KITT, as it was a pretty cool app. i think i deleted my older backup file before because it had a bad licensing error if i side-loaded the backup without Play working properly.
FYI, don't let 1Mobile update any apps you downloaded from Play in the past. you'll get a nice little 'Application Not Installed: the app you're trying to install contains a conflicting signature' error.
i am not sure but i think i still have my KITT app on my old Precedent. that phone went dead on me due to humidity and pocket sweat (it was extremely sensitive to it) and if i can revive it, i'll see if i can get the APK off of it. not sure if the licensing bug still affects it though.
I used to blame Android. coming from an iOS lifestyle i was so quick in the past to say things like 'my iPhone/iPad never did that!' whenever something namely Google Play would act up. however the OS and the Play Store are two different things. Android as far as the actual SDK that you can run in an emulator runs without Google Play or any Google Apps. the Gapps.zip is a separate flash and you cannot blame Android. blame Google and the Gapps themselves. Android isn't the problem.