nice,i wonder if editing the .ppl in the tilesets will doit.
The GRPs for the unit graphics are made for the red player - player 1 if fixed order (player 0 internally). There are 4 palette entries used that are shades of red. For the other players, these 4 entries are switched for 4 shades of the other colors - blue, teal, whatever.
My guess is that the color indicies in the player minimap color byte array come from the same source as these alternate colors, and as Messiah's B2P mod works on the mini-map also I would assume the MPQ's are where these values originate.
Without testing it, I think you will find that if you change that color in the the source palette, you will change the mini-map color and also the color for that shade of grey on all the black units - hence Messiah's mod works by changing both the unit display colors, and the mini-map colors to pink.