My Android ICS phone has 42MB available (according to Settings->Storage). I am not able to install some new apps (e.g. O2 wifi, size 4MB) or update some existing apps (e.g. TouchPal X, size 19MB) though I have been able to install other small ones (e.g. Terminal Emulator, size 1MB and Cache Clear 5MB). I've tried using Cache Clear to clear the caches. I've tried 'pm set-install-location 2' to default the install location to external storage (currently it's 0 i.e. auto) but it's rejected it with the comment 'killed'. I've moved all the apps (that I'm allowed to move) to the sdcard. I'm not able to root the phone (ZTE V790) as I haven't found any instructions & software that works. I'm at a loss what to do.
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