Couple of options here:
1) Have the image you use have transparent arears, then changing the
backcolor will show through them. This isn't good for changing small parts of
images with transparency.
2) Have a set of images in an image list which are all the different
possible images, then when the user selects the color (or whatever causes the
change) pull out the correct image and set it to the button. This isnt so
good for uses with a large number of possible settings.
3) Have 1 icon which is the one you want to display and either:
a) Pick a reserved color like a garish pink which you wont use in the icon,
set all the pixels that should change color to this color. Then when the use
picks the color, you can iterate through all the pixels (suggest unsafe
pointers here for speed) and change the ones which are the reserved color to
the chosen color. I think this is called 'color transplanting'
or
b) Have a second black and white (as in 1 bit per pixel) version of the icon
and iterate through that one setting all the pixels in the main image to the
user color which correspond to a white (or black) pixel in the second image.
This is called masking and allows you to use any colors in the main image.

I know the option used for making odd shape forms like media player is
masking but rather than changing the color it alters the region. This works
fast enough so I imagine it would be real quick for a little image like a
toolbar icon. definatly worth pinning the image and using pointers for moving
through the pixels though. There is a basic example here

for doing image filters but the invert filter should be a good starting
point for what you want.

HTH