For those of you on a shoe-string budget, you can get a freeware paint program from here:
http://www.supercable.es/~cuenca/mpaint.html

It's not Photoshop, not Color-It!, and not even Gimp, but it does work and is only 1.4MB.

Cheers,

I think Pixen is worth mentioning.
http://www.opensword.org/Pixen/
The best low pix. editor I have tried this far, although it still got some bugs and drawbacks.

That is a very good editor, that is.

On a similar note, I recently came across a free app called Seashore which isn't quite the GIMP either, though it is based on the same tech, and is OS X native (unlike the GIMP).