Sounds like a problem in the palette objects... From what I know, each square in them should be 4x4 (since PaletteScale is 4), the columns organized from darker to lighter and the first column of colors in it should be exactly the colors of the character.
Try comparing the code to the original to see if you missed something about it works. Also, I'm not too sure on this, but it seems more fps-friendly if, once it works, you set it up to the game only activates the palette cycle for the current character.