To change the background color, you make the background unique and the exact same color. Then use flood fill to change to any color you want. PC graphics are best for this. If you save in lossy formats even once, things will be a messy if you want to do this. You will have to edit by hand on a low-end editor like I suspect most people have. A high end editor, like Photoshop, can do a range of color values for auto transform of color, background or not. It can handle intensity, shadows, etc. with no problem. But Photoshop is expensive, complicated, personally, I rarely ever use it.
I use low end, simple, fast stuff... even a screen capture program. There are dozens of shareware programs at places like download.com.
For Icons and Avatars, I always edit by hand. Machines cannot decide properly in many cases, even photoshop.... and especially if the background was not generated by machine (e.g., uniform), or saved with a lossy process, or transforms like anti-aliasing, smoothing, blur, sharpen, etc. have been applied.
