Android: Analizar el error al analizar el manifiesto. Descontinuación de la instalación

Sé que esta pregunta se ha pedido a muerte aquí, pero soy incapaz de encontrar la solución en todas las respuestas ofrecidas y su conducirme loco.

Tengo una aplicación que he configurado para descargar actualizaciones de mi propio servidor. Esta actualización se instala bien en algunos tipos de teléfonos pero falla en otros (es decir, el Droid Incredible 2).

• ¿Cómo referenciar una cadena de otro paquete en una biblioteca usando XML en Android?
• Cómo definir parcelable de tipo de interfaz en el archivo .aidl?
• Estructura del paquete de patrones de Android MVP
• Eclipse Java - nombre de paquete no válido - Palabras reservadas en el nombre del paquete
• ¿Cómo instalar aplicaciones con el mismo nombre de paquete en android?

El error que alerta cuando intento instalar una actualización en algunos teléfonos es:

"Parse Error: Hay un problema al analizar el paquete."

El logcat muestra:

INFO/ActivityManager(1482): Starting activity: Intent { act=android.intent.action.VIEW dat=file:///mnt/sdcard/download/application.apk typ=application/vnd.android.package-archive cmp=com.android.packageinstaller/.PackageInstallerActivity } from pid 4620 WARN/PackageParser(2528): Skipping dir: /mnt/sdcard/download/application.apk WARN/PackageInstaller(2528): Parse error when parsing manifest. Discontinuing installation 

1. Estoy firmando y exportando esta aplicación con una clave válida, utilizando la herramienta Eclipse, con MinSDK versión 3.
2. Estoy cerciorándose de que el código de versión en la aplicación descargada sea mayor que el de la aplicación existente.
3. Me estoy asegurando de que el nombre de archivo .apk sea el mismo en ambas aplicaciones.

¿Qué más podría estar haciendo mal?

Editar: he subido esta aplicación al Android Market … cuando intento instalar en los teléfonos con problemas, obtengo una alerta diciendo que "el archivo del paquete se ha firmado incorrectamente". En los otros teléfonos, descarga e instala muy bien.