What programs can edit textures?

On totalwarforums.com, there is someone who wants to create a new Roman family, as a new faction. I told him that it should be possible, but he'd need to get rid of one of the old factions, and if he wanted new colors, he'd need to do texture editing. So which programs can do simple enough texture editing to change unit colors? And, if he'd need a plug-in to edit the files with the program, where can I find it?

Any graphics editing program that can use the nVidia DDS plugin to view dds files. Photoshop is the most commonly used program, but I think the DDS plugin can be make to work with PaintShop Pro as well with some fiddling.

GIMP http://www.gimp.org/
good thing is, its free, opensource and it works on other OS like mac and linux too.
There is a DDS plugin for it but you need to install (yes free also).