For those getting an insufficient storage error in the Google play store or when side loading, which only affects specific apps (not all apps, which has been discussed elsewhere) the following may work for you.
The error is caused by application data folders, which you will have to delete and then reinstall the app. Steps to fix are below:
1) Uninstall the app in the app manager
2) Using your favorite file explorer with root access navigate to /Data/app-lib/
3) Find the folder, which corresponds to the package you have having issues with (for instance com.adobe.reader-1 for adobe reader) and delete it
4) Reinstall from the android market
5) OPTIONAL - restore backup of your data from titanium backup.
Hopefully this will prevent you needing to reflash the ROM and format storage, which i was about to do before rooting around in the app-lib folder and noticing the folders for uninstalled apps that I could not re-install were still there.
Last edited by Dav_prime; 18th March 2013 at 05:35 PM.