Te dice que no está instalada por que has roto la firma de la apk y no puede instalarse...
Seguro as descomprimido todo el apk y después lo has vuelto a comprimir, cambiando la extensión zip por apk no? MAL! Así se rompe la firma.
Te explico más despacio:
1 abre la apk con 7zip y busca la carpeta donde se encuentra el icono que quieres cambiar, deja la ventana abierta.
2 arrastra tú icono personalizado sobre la venta abierta del 7Zip
3 cuando termine, instala el apk.
Saludos!