Indexalo con CMP o Irfanview, luego de eso importa la paleta nueva y reemplazala por una existente, luego exporta el tileset y pega los tiles nuevos de la misma paleta.

Tu problema es que debes de poner tiles no indexados sobre el tileset, aunque usen los mismos colores, pero si no estan indexados estos solo seran siluetas negras.