Why is "insufficient storage" wrongly reported when installing an .apk via adb?
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.