Bear in mind I'm a complete Noob when it comes to graphics editing. Assume I know nothing about anything in that area. I did manage to do a creditable red mail and plate by using floodfill in PSP. I'll check out the vertex coloring thing... is it a function in BRF edit?
Yeah that's why I'm suggesting to use that possibly as a placeholder. Anyone with graphics editing skills would do much better in Photoshop; a good recolor probably takes an hour tops for a skilled person. Not to say you can't sometimes get good results with just vertex painting; the red and blue gambesons are products of vertex painting. But you kind of need the base item to be light colored and you lose the highlights so it tends to have best results on non-reflective costumes like cloth leather etc.
"Vertex Painting" is the box on the first page of BRF Edit. Can't miss it. Select your color, paint mode-> Paint, and click on your model to spray red onto it.
If it looks like you're making everything look bloodstained, that's because that's exactly how the game engine paints blood onto your clothes.
P.S. Your "red company" theme is somewhat similar to what Hardcode and I had in mind for our revamped Sword Sister line - a variant of troops which only the player can have, which have unique capabilities: in our case, the ability to be completely adaptable and be able to reconfigure from mounted to foot, melee to ranged, etc with player commands.