Unfortunately, the Gimp sucks for indexed graphics (using palettes) and I really hate its user interface.
Bad palette support is also true for Photo Filtre (
http://www.photofiltre.com/ - free for private use), but in contrary to Gimp, it's a small, quick, crash free and intuitive painting program.
When it comes to commercial painting programs, I think the best for game programming are PaintShopPro and Pro Motion (
http://www.cosmigo.com/promotion/). PSP has more features and the palette support is ok. Pro Motion is pretty much like Deluxe Paint on the Amiga (and can even read Amiga ILM animations) with very good palette support. Still, I prefer PaintShopPro...