I usually use the GNU Image Manipulation Program, or GIMP. While it's basically an open-source photoshop alternative with varying quality, I can save palettes for use on indexed images and I can use layers to prevent reverting any changes should I want to edit the background without the foreground. There are a fair few techniques that the layers also contribute that help me achieve some of the effects.
I also find it handy for making full-color images or concepts that I'll later reinterpret or convert into an indexed image, due to the freedom offered by dodge/burn tool as well as the smudge tool.
Paint.net may have these as well, but I know for a fact you can choose just how many views you want to have. Normally I have layer and colormap dialogs open, as too much else would over-complicate things. Now I have nothing personally against MS Paint, but I cannot live without the keyboard shortcuts that GIMP has. (ctrl-click draws a color, space click moves the canvas, etc) Additionally, I find Paint's palette options a tad limited, though I haven't tried the Windows Vista or Windows 7 version.