There is mtPaint, specifically created for making pixel art under linux.
http://mtpaint.sourceforge.net/It has some pretty nice palette features, but I found it was missing a few key tools that I use (can't remember exactly what at this point, I should give it another shot and write a proper review

).
I use the GIMP, which works pretty well once you get a good layout, stick it into indexed mode and work out how to use the palette interface. It just lacks some of the nice palette features in other pixel/index specific programs (Deluxe Paint, Pro Motion, GraFX2, etc). Probably should write a plugin for it (or just fork the damn thing), but I doubt I could be arsed.

Anyhow, as for MS Paint... yeah, you can make pixel art with it. You can also make pixel art with NeoPaint for DOS, or a hex editor, or lego blocks. Very few paint apps are specifically designed with pixel art in mind, so if you're not going to use one of them then you might as well use something that has a decent feature set. Things like: layers, for example, or good configurable shortcuts, transparency support or any number of other things that will make your pixelling easier, none of which MS Paint has that I recall.
We pixel artists make things arbitrarily hard enough for ourselves as it is, we don't need to make it worse by having to fight to make the program do what we want. But hey, if you know how to fight MS Paint well, then use it. Do what makes you happy.

... that post was way too long.