Consejo: Probad a cambiar los iconos dentro de la ROM sin sacarla fuera. A ver si me sé explicar, teniendo la .apk dentro de la ROM y sabiendo los iconos que se quieren cambiar hacerlo dentro de la ROM, así cuando se firme la ROM se firma todo. Personalmente he cambiado todos los iconos de mi ROM y de alguna que otra .apk y siempre lo hago desde dentro de la ROM. Lo primero que hago es sacar la carpeta res al escritorio para saber o familiarizarme con los iconos que quiero cambiar, pero la .apk sigue dentro. Sabiendo los iconos que quiero cambiar y dejándolos a la misma dimensión y resolución los cambio dentro de la ROM ya que si un .apk le hacemos doble clip dentro de la ROM se nos muestra como un archivo .rar en mi caso y otros .zip. Luego en las ROMs Sense dependiendo donde se coloque la .apk te la instala o no, si la .apk es del sistema lo pongo en la carpeta app_s y si la .apk que he modificado no es del sistema la pongo también en la carpeta app_s sino no se instalara y las .apk que no modifico las pongo en la carpeta app. Pero todo lo hago desde dentro de la ROM sin sacar la .apk de ella, tan solo saco la carpeta res de la .apk para saber los iconos que tengo que cambiar...
Un saludo!!...