A not just re-color! Edit of Moltres!

[Chutzpar]

What you should be taking away from the original sprite (and subsequently trying to apply to your own original sprites):
Line quality; specifically, the use of selout and anti-aliasing.
From the spriting dictionary thread (thanks Gors c: )

SELOUT (aka selective outlining)- It's a technique where you 'select' the outlines that will be shaded. Used correctly, it can make your sprite to look more 3D than it would with plain black outlines.

See how the first sprite looks rather flat, even if shaded properly. That is adressed painting the outline with colors (image 2). Keep in mind that the lines away from the light are darker than the lines near it.
Notice that parts of the outline are black and some aren't. Those black parts are placed away from the lightsource, in solid objects and/or defined places, acting like outline thickness used in traditional art media.

ANTI-ALIASING (aka AA)- It's a technique where you place mid-tone pixels in strategical places to make the line smoother.

In this case, the black line is anti-aliased by gray pixels placed on the 'corners' because the background is white (white+black=gray). If the line was red, then the gray dots should be changed to light pink to properly anti-aliase it.
Keep in mind that that image example was generated with Photoshop, so there's a lot of midtone pixels aliasing it. In spriting, obviously you'll want to use a less extreme AA. Only place them in jagged places; if the line is already smooth without AA, there's no need to do it.

I did your homework for you and zoomed in a bunch so you can see what's actually going on with the sprite you edited:

Selective Outlining: notice how some of the lines on the body are done in brown? That's where something either has less weight, or where it's in less extreme shadow.
You can see Anti-Aliasing on the wing; notice how the same brown colour is used alongside the black, to smooth out the edges there. If it weren't for that, it'd look jagged.

You should also pay attention to its palette.
By the looks of things with your blues you've just used a darker version of your base colour. Don't do that. That'll make things look flat and sort of lifeless - pay attention to the colour of shadows in real life. Are they just darker versions of the lit parts?
(the answer is no)

So what do you need to do? Hueshift. Explanation from the Spriting Dictionary thread, again:

HUESHIFT- Hue shift, as the name implies, is shifting the hue.

look at this wheel. rather than increasing or decreasing a color's saturation, or its Contrast, you switch to the color to the right or the left on this wheel. Notice also that colors on the exact oposite of the wheel also work as a darker/lighter version of your color. A more dinamic and natural palette of colors is the result of a proper hueshift.
Note: HUESHIFTING can be combined(an to an extent, has to) with CONTRAST and SATURATION in order to produce a wider vaiery of results.

Again, I've been nice enough to do your homework for you, and put up a (slightly incomplete) palette from the Moltres sprite:

The second line's probably more obvious than the first; in the second you can see that it starts orangey and shifts more towards pink and red hues
the top line's more subtle; it goes from a pale pure yellow and shifts ever-so-slightly towards orange.

Aside from just plain old looking nicer, this is a way of increasing the contrast between lit and unlit areas without having to go too dark, tonally. Using too many dark tones will mess with your readability.

---

Short version: Don't just edit and recolour unthinkingly. You need to pay attention to how the artist approached the sprite you're looking at, and understand why they used certain techniques.

Definitely, definitely look at the Spriting Dictionary Thread, it's stickied in this forum.