Insufficient storage when installing app on Android ICS phone
On an older phone of mine this was an issue with the app store. Insufficient storage error was fixed after an update. One app, HuffPost, had poor coding and gave me that warning. Many updates later they fixed it.

You can use Gemini App Manager to move app to the SD card that Android won't allow you to: https://play.google.com/store/apps/details?id=com.seasmind.android.gmappmgr

Edit: Found a root guide. http://forum.xda-developers.com/showthread.php?t=2138234