Neste tutorial pretendo ajudar quem não souber a fazer Recolors de sprites. Vou fazer o tutorial no Photoshop mas escrevi no título "MSPaint" porque não há aqui nada que não consigam lá fazer, e nem todos têm acesso ao Photoshop. Continuando, como base, vou apenas dizer aqui algumas regras básicas do spriting:
1 - Nunca se aumenta ou diminui o tamanho de um sprite: enquanto estás a editá-la, faz zoom, não a aumentes. Um sprite aumentado ou diminuido fica deformado. Exemplo.
2 - Nunca guardes um sprite como .jpg ou .jpeg... fica com uma qualidade terrível, guarda como .png ou .gif.
3 - Nunca pintes o background, deixa-o transparente.
---
Para começar, faz zoom à imagem ao teu gosto (eu gosto de trabalhar a 300%, 600% para tratar de pormenores) e faz a palette das cores. Se não souberes o que é está aqui uma imagem de exemplo. Para este tutorial vou usar um Qwilfish.

Decidi pintá-lo com as cores de um Donphan, de tons de cinzento, então vou substituir a parte de cima, a azul, pela parte cinzento-esverdeada do Donphan; a parte de baixo, amarela, pela parte cinzento-clara do Donphan; a parte vermelha, da boca, do tom vermelho também do Donphan. Ora substituindo cada cor pela sua respectiva substituta, deverá ficar assim:

Não é preciso olhar com muita atenção para ver que ainda há algumas falhas, nomeadamente no outline e um terceiro tom de shading que não existe na parte cinzento-clara do Donphan. Quanto ao outlining é fazer o mesmo que um recoloring simples, exceptuando a parte direita da cabeça do Qwifish, onde a cor de outline seria igual à cor adjacente do corpo. Neste caso terás de ser tu próprio a criar um tom intermédio entre o cinzento original e preto, criando um cinzento mais escuro.
Nos pixels amarelo-claros na parte baixa do Qwilfish terás de fazer o mesmo, encontrar um tom intermédio.

E parabéns, apaga a palette, devolve a imagem ao zoom normal e compara os resultados.

PS: Guarda-a como .png ou .gif, não te esqueças, nunca .jpg ou .jpeg