Your sprites are looking a lot better, especially the second one you posted. I agree with what the person above me said, a more interesting color palate would do these sprites some justice! Look around on pixeljoint.com to get some ideas for your palates. The key is to shift the hue as you transition from dark color, to light color.
Here's a good example of an interesting color palate:
http://pixeljoint.com/pixelart/97961.htmTake notice of the colors used on the shirt. In order from dark to light the hues are as follows: brown, green, brown, red blue, white. The masters have a way of selecting colors that create such interest, a single hue does not limit them.
Now you don't necessarily need to go to this extreme for your sprites, especially as a beginner, I think they would do just fine with simple shifts in the hue from dark color, to light. Experiment, see what you come up with
