there is an easy way to do this in photoshop.
I don't know anything about your sprites, but here's the simple way to do it in photoshop.
let's say I'm making fire sprite. It is 64 pixels high and wide and has 10 frames of animation. To get them all on the same palette, I'll make a photoshop document 64 pixels high and 640 pixels wide. 640 being 64 times 10 frames. Next I copy and paste all of the frames in order next to each other in order. I use the grid to make sure they all get their own 64x64 space. Then I go to [Image] > [Mode] > [Indexed Color...] which turns it into the 8-bit mode we need for sprites. Since all of the frames are in the same document, they get the same pallette. Crop each frame and save the each seperately and the rest is quite easy.