Si te sale la aplicacion no esta instalada puede que sea por que ya tienes una igual instalada, desinstala la que tienes en el telefono y despues mete la que estas modificando, por si las moscas, firmala tambien, para eso e puesto la opcion
Ya me comentaras si te funciona, la verdad el apktool y android en general son muy "tikismikis" con estas cosas... podrian hacerlo mas facil :S
PD: La instalacion del programa es como la teneis, primero se instala la version final, despues el Update se instala encima, asi siempre que se saque un Update.