This question already has an answer here:
I have an HTC Desire running Froyo. It is not rooted, nor have I installed any custom ROM.
I get an "Insufficient Storage" error when I'm trying to install an app via adb/eclipse. The .apk is only 300KB, and the phone reports 14MB free of internal storage, and 2.2GB free on the SD card. (I have just uninstalled a few large apps to make sure there's plenty of room.)
It is obviously completely wrong. There's easily plenty of room in the 14MB of internal storage for my 300KB app.
What can I do to fix it?