I have this problem too i used Marketfix and now i can install all apps but for some reason i cannot install Titanium backup its the only one that says "Insufficient storage available"
No solutions up until now yet, but the real culprit is the cache created by google playstore in the cache partition when downloading apps.
I found a workaround to use until google sort out this bug. I backed up all of my apps, do a factory reset,and restore the app. In order to prevent google playstore to build up it's cache when downloading new apps, i use an apk leecher, transfer the apk to sdcard, and install from sdcard. Sometimes i have to use market fixer to link some installed apps to playstore. i preserved the cache for updates only.
not very pretty and i don't like this, but at least it worked.