If I recall, each "family" of textures had its own 8 bit palette in a separate pcx. All texture files within this fam would have to confirm to the color range in this palette file.

So it sounds like this particular one is something I forgot to format correctly. Apologies. Have a screenshot?