I use GIMP for all my 2d needs. It can be a bit daunting at first but once you get your head around all the features you can produce some lovely pieces of art! My advice would be simply practice, practice, and more practice! Don't be afraid to experiment with features, and if you need help with a particular feature or activity, there are usually people hanging around in #public-art who can help :)
I use Photoshop far more often than Gimp, but I also use a lot of tools that are either not available to Gimp, or are extremely unstable in Gimp. But, just starting out, Gimp most definitely is great for learning how to do recolors.
If you are going to do just recolors GIMP is fine and more cost efficient. I spent over 600$ for my copy of photoshop but I do a lot more with it so it was worth the cost to me but to a beginner yeah no
I like Paint.net (PDN) too. It's free, there are a load of tutorials and plug-ins available and I just found it all round better than GIMP. Also the newer versions are far easier to use than some of the older ones were. My girlfriend started with PDN and she's a bit technophobic, she now has to use InDesign for work and found some of the things she learned from PDN gave her a better understanding of this kind of program.