Bueno, lo más facil que puedes hacer es guardarlo en .bmp, pero en mapa de 24 bits.
Si guardas en otros formatos .bmp, se te arruinarán los colores.

Hace eso, o en vez de guardar en formato .png directo del paint, lo guardas desde el photoshop en modo indexado.