The INSTALL_FAILED_INSUFFICIENT_STORAGE error is the bane of every Android developer's life. It happens regardless of app size, or how much storage is available. Rebooting the target device fixes the problem briefly, but it soon comes back. There are hundreds (if not thousands) of message board posts from people asking why the problem occurs, but the folks at Google are frustratingly silent on the issue.

There is a simple workaround. If your test device is running Android 2.2 or later then add the android:installLocation attribute to your application's manifest file, with the value "preferExternal". This will force the app to be installed on the device's external storage, such as a phone's SD card.

For example:

  <manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.andrewsmith.android.darkness"
    android:installLocation="preferExternal"

This is more of a band-aid than a fix, and it may not be ideal if you want your finished app to install on the device's internal memory. But it will at least make the development process a lot less frustrating.