I'll be honest with ya. In terms of just a recolour, this one isn't that good. I assume you're using Paint, right? Well, the best thing to start with is by learning to NOT use the default colour palette.
The three greens you used are all default ones, and quit frankly the way you've done them just looks bad. Unless you're going for that "retarded super bright green" look, you'll want to get something dimmer. You also want your colour choices to make sense. For instance, look at Red's hat. On the edge of the peak, the sprite uses a dark blue. This isn't being used because of aesthetic reasons. It's to act as a shadow of sorts (If you look at the larger sized sprites of Red, you'll see what I mean. I'm pretty sure I know how that happened, but it's ok. It can be fixed. Before I get into that, though, you need to know how to get your own colour options out of Paint.
On the menu, go Colors > Edit Colors. You'll get a pretty box with lots of default colours. Near the bottom of the box is "Define Custom Colours >>". Clicking it gives you more. Now you can choose more colours. Do this and get yourself off those default colours. Also, don't use colours that are extremely similar to one another. Your two bright greens, both defaults, are like this.
You'll need to figure out how to get your colours to work together. To help you out a bit, though, try working with a colour than messing with the shading via the slider bar on the far right of the Edit Colours box.
Now to actually fix things. The one problem I noted was the hat's peak. That bright green can't be there, because it's not even correct. Start by manually replacing it with your dark green (Note I'm assuming you're off the default colours but using the same general idea). This alone will improve the look of your recolour greatly.
To help you out a bit, I did some slight tweaking to your recolour, and put it along with your original and a sprite of Red. I also included a colour guide so you could tell what colours were used in each sprite. I could've organized it better, but meeh. Too lazy at 5 AM.