Photoshop CS3 es la herramienta perfecta y modificar un .png es muy sencillo,es igual que retocar una imagen .jpeg normal,solo que la .png tiene las transparencias (los cuadritos de ajedrez por detras de la magen) y puedes hacer la forma usando la herramienta ''Goma de borrar'',con esa herramienta vas pasandola por la imagen y vas borrando lo que quiera,lo que queda detras es transparente,ya lo demas es igual que cualquier imagen!
El tamaño de lo que estes editando debe ser el mismo siempre,si editas un icono que mide 35x35,esa medida es la que debe conservar,a la hora de guardar,seleccionas formato .png,lo dejas todo por defecto y guardas...
Yo mismo he llegado a editar algun Theme de Theme Chooser para CM7 usando Apktool creo que era... con eso descompilaba el .apk y me ponia manos a la obra,despues habia que recompilar de nuevo,aunque muchas veces esa herramienta fallaba mucho al compilar dando errores...