Duplicate of Play Store 4.9.13 insufficient storage error and icon issues
But my rep can't comment yet, so I'll repeat my answer:
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:
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!