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).

• Cambiar el nombre del paquete dentro de un APK
• ¿Es posible distribuir una clase genérica?
• Problemas al enviar el paquete con PendingIntent a un receptor de difusión, datos perdidos
• ¿Cómo instalar aplicaciones con el mismo nombre de paquete en android?
• Pon el Objeto como intención para la siguiente actividad

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.