I will presume you have meant software tool, if you didn't then ignore the following.
If it can make a pixel on the screen in the color of your choice, then it is a viable candidate. You will find though, that there are certain functions in different programs that will make your life easier.
Here are some possible packages:
MSPaint - You already have this. It usually does what it is supposed to, which is not all that much. If are really good, you can use this nearly as effectively as any other tool.
Pro Motion - Buy it. It is good. Pixel painting program, similar to dpaint on amiga. Also known as index painting software, as it allows a lot of complex effects through a palette system. I like it simply for the color switching and animation. As the name suggests, pro motion is geared towards animated sprites.
Photoshop / Imageready - Buy it. It is great. Once you learn photoshop you will understand why it is the staple program of most designers and digital artists worldwide. Even a lot of 3d art comes back through photoshop for finishing. Its range of tools, effects and the refined interface are that which only about 15 years of development can bring. It is overpowered for pixelart, and animation is lacking. Imageready is supposedly an integrated animation package, but it is not designed for sprite animation as we do. It has a layer based animation system, which I find fairly difficult to use. It also cannot export in anything but GIF (why why why, it can import many many formats. adobe, this is stoopid).
Graphics Gale - It is apparently great, and is in Japanese or something, which turns me off slightly. It helps to be able to read a menu.
Paint Shop Pro - I used to be a fanatic, but that was before I got photoshop. nuff said.
Photopaint - I lied with previous, it was before I got this. and THEN I got Photoshop... this is nearly on par, but is a pale imitation. Corel should stick with vector, it is clunky and bad GUI.
Telepathy - I have not had much success with changing the color of pixels with mindpower. Give it a shot though!
There may be others. Let me know.