Often times the select screen when it depalettizes uses the palette of player 2 when you start a P1 game. It never messes up so long as you start a 2P game, or a 1P with P2. I have no idea why that happens.
If you notice, for whatever reason Shang Tsung uses the exact same palette format as the female ninjas. If you were fighting Jade as P2 in the match before, there's a good chance that's why. I know it happens when Shang is P2 and you get the Tanya look. I've played 35 matches in a row before at home vs people without a single glitch on the later mames, but it still happens occassionally. I really don't understand why mame dev doesn't fix that.