Credits to Sudo SU Root!
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 <--EXTRA
OR
/data/app/example-app-2.apk
/data/app-lib/example-app-1 <--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!