Try this (it works when you get "Insufficient Storage Available" error, maybe this trick works too in this case) :
1) Close Play Store
2) Sign out (remove) your google account in settings
3) Clear Google Play Store data in settings
5) Sign in to Play Store with your account
6) Try downloading some apps
Hope this works..