Thanks, done and no effect. :'(
You are RIGHT there. Just click on storage and you will see it! FIRST try clearing just the cache, see if that fixes it, THEN try clearing the cache on Google Play Services (same procedure) then in the same order try clearing data, BUT clearing data wipes out a bit of stuff like saved passwords, and game progress and stuff. (SOME games save progress on a server so no worries your Clash of Clans Town Hall will be fine, although you might have to attach to it again as you did first time you got a new device)