The gimp is a decent program I hear, mspaint isn't complete shite, but nothing compares to Photoshop in my opinion. I would even say the built in editor in C2 is almost decent enough, except no hotkeys (that ive found) to do things like sample, manipulate individual selected objects or layers, which is very important to me. Pixel art really just requires great patience and a good workflow. I would reccomend doing some google searches for pixel art tutorials. You'll find it's ultimately less about the tools you're using and more the workflow and artistic skill that creates good art of any kind. Good luck in your search
Austin Morgan
Varia Games