I think the original was fine, but I have no problem with the slightly altered colors, as long as gradients are NOT considered. Gradients make baby jesus cry, especially when the style was intended to be cel-shaded.
The only problem is, as Camus said, it'd help to see more sprites in this style. Possibly an animated version of this sprite would make it a that much more awesome, like a dance or seductive walk of some sort.