....
si los gif son muy diferentes sus colores y en efecto solo tienen 64 colores cada uno, lo mejor es hacer una paleta que incluya los colores de ambos, podes dejar que photoshop la haga por vos, hace un archivo nuevo y ahi pega las dos imagenes, aunque sean estaticas, de ahi convertis esa imagen en index para que te haga una nueva paleta de color. cuando te aparezca el cuadro de dialogo pedile una paleta local adaptiva, y le das ok, desspues repetis el procedimiento para exportar, esta nueva paleta tendria los colores de ambos gif y no te deberia dar tanto problemas importarla en ambos archivos... y no vas a tener que estar dando tanta vuelta...