¿Por qué se informa erróneamente de "almacenamiento insuficiente" al instalar un .apk mediante adb?

Al menos en mi teléfono, parece que se necesita mucho más espacio disponible que el tamaño de la aplicación que se intenta actualizar. En mi caso, parece que necesito tener al menos unos 13 MB de espacio libre para actualizar cualquier cosa (incluso para aplicaciones de 500 KB).

Algunos consejos para liberar espacio:

1. Ve a Ajustes, Aplicaciones, Gestionar aplicaciones, haz clic en "Mover a tarjeta SD" en las que tienen esa opción.
2. En la misma lista, haz también clic en "Borrar caché" en todas tus aplicaciones.
3. La caché de tu navegador no se puede borrar aquí, así que abre tu navegador, ve a Configuración y haz clic en "Borrar caché".

En algunos casos también he podido actualizar manualmente las aplicaciones de una en una cuando "actualizar todo" falla por falta de almacenamiento.

Estás intentando instalar el .apk desde una fuente distinta al directorio Root. Copie el .apk en el directorio Root e instálelo desde allí.