Si no la pudiste firmar no funcionara y es por eso que no se instala, a mi me paso igual y era por no haberla firmado, al poder firmarla ya la puedes instalar, sin embargo yo solo vuelvo a meter la app a la ruta de donde lo saque por ejemplo "system/priv-app" y dar los permisos correspondientes, reinicio y las modificaciones se cargan y listo.
Uso apktool 2.0 y no me problemas para firmar...