Let’s recap, each team color represents for each Co-Op Commander:
What if Dark Grey for the new Co-Op Commander, Tosh? Also, Rohana has the same team color as Raynor.
Artanis and Nova are more Cyan.
Teal is the color for Zeratul (that happen to be missing from your list).
For purple/violet/pink, I could question it, but it’s too much in the subjective zone.
Alarak is Dark Red, which allow him to not be mistaken as an enemy as much as Mengsk 
Stetmann is orange.
For new commanders, for having played a bit with the White color using the color blind system (especially to not confuse Mengsk ally with the enemy), I think that color would be nice if used, though not especially thinking of Tosh.
I feel like Black/Dark Grey may somehow be avoided by Blizzard (or maybe it’s just it disappearing between Warcraft 2 and Starcraft, and not reappearing easily in Starcraft 2, that make me think so), so if it’s the case, need to think of alternatives.
Probably because it blends in too much when turning off the terrain on the mini map.
You almost had me there NGL.
Hm, I’ve been switching the Colors settings for a while now so I may mix them up, but I’d say default Nova is more Blue Grey.
Zeratul is the Aquamarine color in the menu (so teal/turquoise, given the Teal ingame is rather cyan).
Mengsk got his own named color between red and brown.
And I’ m not sure since I don’t see them often but I’d say H&H got the Rose one (which also seems between red and brown but color perception is pretty subjective, yeah).
Wasn’t the UED in Brood War black and grey?
Brown and white according to starcraft fandom (I’m too lazy to check in actual maps).