Epic 3-month old necro in the post above.
Hey Esco, I was just looking through this and saw the post about palette cycling. Have you tried the GIF Hard Edit method yet where you open the GIF file the sprite is stored in and rewrite the palette data?
The other method I'm considering, although I haven't gotten around to using it yet, is to create the palette-swapped enemy sprites when you transition from room to room, then delete the sprite when you transition to the next room. It might still be slow, but it only makes extra sprites for the enemies in the current room rather than all enemies. As long as you don't flood a room with four or five different enemies, this should in theory work fine. This of course would only be necessary if creating a single-frame sprite on the fly would be too slow during actual gameplay.