Technique for this problem is something I have been seriously considering for a very long time.
The obvious method as given above is simply to do a fuzzed color replacement. This works very well, but generates 'aliased' or thresholded edges. That however is find if you plan to save the image as a GIF image on transparency.
It also works very well on very very large images such as what you have provided, as after color replacement resizing the image smaller will restore the anti-aliasing (semi-transparent) edge pixels.
However this technique fails badly when the image is already small and will not be resized smaller! It is in these situations I have been trying to come up with ways of
recovering the original pixels before they were mixed with a known background color.
That is I am looking for way of subtracting a specific color leaving 1) the correct semi-transparency 2) the original color.
The technique Masking with Anti-Aliased Edges
was developed with this goal in mind, but is only designed to recover the transparency, from wimages with a fixed color (usually black) border.