Using
this, I found that the following were supported on Linux:
GIMP
GIMPshop ('GIMP designed to look similar to Adobe Photoshop')
CinePaint (a GIMP fork)
KolourPaint (which seems a lot like MSPaint)
Krita (which WP says is similar to GIMP)
Mootif (not much info)
mtPaint (looks similar to GIMP)
Photogenics (probably crap)
Picasa (wtf, not even an image editor)
Pixel image editor (costs money)
Tux Paint (meh, seems similar to Kid Pix.)
KolourPaint looks the most promising out of those.