Sprite Help

[German Man]

I have some sprites of Igniz from KOF.  My problem is i want to remove the background color but it is the same as a lot of the colors on the sprite itself.  How can i remove the background color and not damage the rest of the sprite?

ex:

[ultimatedude]

Change background colour

[German Man]

I've tried that and that is the main problem becuase there is so much black on his body i get this outcome when i change the background color.

ex:

[ultimatedude]

Well, what idiot made the background black when his outlines are pure black too...?

Unless its a transparent GIF, which in that case try opening with photoshop, fireworks or whatever