Ok, after much messing around, I came to the conclusion that John is right, and the dark colours don't show well on the minimap. Even the existing purple is not so visible...
However, avoiding all dark colours severely limits our choices, and makes it near impossible to come up with 16.
Interestingly, white is in. It looks fine on the winter tileset, grey was actually much worse, and has been given the boot.
So, here is the current palette... subject to last minute tweaking of course
The colour in the middle is the 'actual player colour', and the colour outlining it used on the minimap, to outline that factions units.
eg,
The ability to switch to a green-blue-red system as suggested might be nice, and wouldn't be too hard to do, but with 16 colours to chose from now, arranging teams by hue should be sufficient I think.