Alright, I'm going to take this step by step.
First off, when returning back to look at this sprite of yours, I find 24 individual colors, most serving no functional purpose and I probably missed a few. How did you manage that? A sprite like this should not have more than 16 colors. I tend to use 10 colors, as during my pixel process that is usually what ends up being what I need to finish the job (keep in mind, all of the projects that I've done are small, for a bigger piece more colors could be used, but still the matter remains that you should always use as few colors as necessary).
Looking back at your first sprite, the AMOUNT of colors you were using was reasonable, though some condensing could be done of the greyscale.
Now color theory is not all about just using a small amount of colors, its using each color you have to it's fullest extent (which means that the colors you use must be chosen extremely carefully). Before you even begin shading, YOU MUST HAVE FUNCTIONAL COLORS TO SHADE WITH. At this point in time, you don't have functional colors to shade with. Before you can even learn about shading, you need functional colors. Once you learn more about colors, then you can learn more about shading.
So, to do list:
1. Clean up the amount of colors you have in this current version, try to at least get it down to 16.
2. Study study STUDY color theory, make a better pallete, there were plenty of color tutorials to get you started posted earlier in the thread by Metaru.
3. Then learn shading.
PS. The shading on this one is still bad, don't worry about it at the moment, but keep this in mind.
Lightsource disagreements again
also, the hat is still a bad gradient
May add more to this later and make an edit, but honestly I really shouldn't have to because everything you need to learn is summed up in 1up's edit, you just have to take the initiative to learn on your own. If you can be patient and not rush a sprite because ""you have to have it"" you could learn a great deal more, and learn it yourself instead of having others spoon-feed it to you.