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.
At least on my phone, it seems you need way more available space thanthe size of the app you are actually trying to upgrade. In my case it seems I needed to have at least ~13MB free space to upgrade anything at all (even for 500KB apps).
Some tips to free space:
Go to Settings, Applications, Manage Applications, click "Move to
SD card" on the ones that have that option.
In the same list, also click "Clear Cache" on all your apps.
Your browser cache can not be cleared here, so open your browser, go to Settings, and click "Clear cache".
In some cases I have also been able to manually update apps one at a time when "update all" fails due to insufficient storage.