Esta es una duda muy frecuente y tiene fácil solución:

Lo único que debes de hacer es guardar todas las frames de la animación (con SAVE IMAGE en el programa) en una carpeta cualquiera. Al guardarlas, también estas guardando la información de la paleta.
Una vez guardadas, debes de tomar el tile que quieres animar y superponerlo sobre la frame correspondiente. Ya hecho esto, vuelves al programa y insertas las frames de nuevo, pero esta vez no te dará el problema de la paleta.

Si tienes algún error mas, dilo. Salu2!