I really depends on whether you want to do a full retexture, or if you just want to add some blood and stuff.
Primarily you need to obtain the original UV map for the character before you go anywhere.
The original artist may have positioned certain aspects of the character in strange places on the UV, so having a nice blank UV map to overlay on the original texture is always useful. For example, I've noticed that bond always makes his textures "overhang" the area they are intended for (to prevent black seams), this means that if you colour right to the edge of his original image, not all of your texture will show.
It's also gonna be a good idea to look at the model in something like milkshape, to see what areas of the texture get stretched when the character is at the extremes of it's movement, you don't want to go putting something like a belt, braces or vein on an area that gets stretched when the character moves - it'll just look horrible.
If you're gonna change one item of the characters clothing, you might as well do the whole thing. For the most part, your stlye will not be the same as the original artist, so your one change will probably stand out. You're probably best re-doing the whole thing, so that the texture style of the model is consistent.
NEVER use flat areas of colour. they just look horrible.
That's all I can think of for now! Peas.
