To give an Photoshop tip for coloring ,
if have photoshop and use, try do with Image Adjustment options
Change the colors with use the Curve menu and Color Balance menu and etc
for example
first off, change image mode to RGB, and make outline of picture exclusive of backgrond
make new layer as copied object which constituted with outline
and change colors on Curve menu first
in the Curve menu, there are 4 channels -RGB,Red,Green,Blue
control Amount of each channels value with Curve interface
if u like first changed color, then try change color balance and Brightness and contrast
then could get changing colors satisfactory
as far as it goes

And notice and becareful, when u change mode to indexed BMP
try change palette set, shadow color and special colors and other unused blue colors should changed to different colors
if don't do like that the pircture could be colored with those colors of palette