Play Store 4.9.13 insufficient storage error and icon issues
The correct answer to this problem, and I always see wrong explanations, is that you have a duplicate /data/app-lib folder for the app or apps that are giving you that error.

To fix: Using adb, terminal, or root explorer:

compare /data/app to /data/app-lib 

you will see, for example: 


/data/app/example-app-1.apk
/data/app-lib/example-app-1
/data/app-lib/example-app-2   &lt;--EXTRA


OR


/data/app/example-app-2.apk
/data/app-lib/example-app-1   &lt;--EXTRA
/data/app-lib/example-app-2


So for 1st example remove directory: /data/app-lib/example-app-2

and for 2nd example remove directory: /data/app-lib/example-app-1

Then your app will install just fine!

ALWAYS REMEMBER TO KEEP THE SAME NUMBERS, 

IF THE APK IS 1 REMOVE 2... IF THE APK IS 2 REMOVE 1!