I thought I needed to break this "symbols" approach out into a separate answer.
Back in the day, I assume people needed flags and stuff to easily identify an army way off in the distance, so you know whether to attack or defend (in case of foes), or be relieved (in the case of allies).
So, incidently that's exactly what you're trying to do. Easily identify something off in the distance.
You can do that with just color, but possibly a better way to do that is with color and symbols. Using a combination of colors and symbols will help colorblind people identify things, as many people mentioned above.
If the units are big enough, you could also go with 2-4 color coats of arms.

The pattern is easily recognizable, not just a color. Good texturing could brand the coat of arms quite large on the chest or upper arm of each unit.
In the image above, the helmets for different units have different geometry, as well as the shield insignia.
You may find also interesting the idea of Japanese Mon, which are very simple looking "logos"

Now you're basically branding your units with modern "brands". StarCraft II did this a little bit with "decals",

but these are barely visible in-game

and aren't used for identifying units so much as colors are.
I'd look at flags as well for inspiration, particularly the ones that don't use a 3-stripe brand pattern (those become a little confusing). Consider:
- Switzerland:

- Somolia:

- South Korea:

These all have some very simple-looking, yet distinctive flags.
Also check out symbols that the American government uses to identify defense staff. These are monochrome images (can be done completely in black and white), so this might actually be a great solution that will not exclude colorblind people (basically use symbols to identify teams, instead of colors)
