Actually, GIMP can do that easily. Just set the image mode to Indexed and give it a 256 color palette (you can make one in about 10 seconds with auto-palette and the palette editor).
If you want to do any actual palette editing, that's probably the one thing GIMP sucks at; changing colors is really clumsy and there's hardly any automation for things like gradients. But Paint doesn't let you edit the palette at all, and it uses the same default palette regardless of the colors in your image...so, yeah.