Scratch my Back?

[DaFool]

I need to replace the palatte of two stock units in the game-the horseman and the enkidu warrior. I need to do this because the colors of shadows on their palettes are the same as the background, and when I export this to the .pcx sprite sheet, it is interpreted as the same-hence no shadow. If I can insert my own pallete or if someone has already fixed the problem, that would be great. Just tell me what to do or where to go.