A ver, supongo que guardas el sprite, lo abres con gimp, vas a imagen -> modo -> indexado, y generas la paleta óptima, asegurándote de que el color del fondo queda como el primero de la paleta. Luego, lo insertas, y dices que se cambian las paletas. El problema puede estar en 2 sitios:
1 - En gimp no indexas bien
2 - No lo insertas bien en Unlz

Estaría bien que postearas unas cuantas imágenes para que podamos ayudarte mejor.