If you use the Windows clipboard to make a screenshot, you lose the palette. Paint doesn't allow much control of the palette either.

Dump the graphics directly from the emulator or a savestate, and use PaintShop Pro (version 4 is already sufficient) or a similar tool to edit the screen.

You're using TLP, aren't you. I used to know how to get around this; basically, it involves extracting the image as a bitmap, saving a copy of palette - one with ALL of TLP's original information, editable in a text editor, then making a copy of THAT and replacing all of the "extra" infromation with zeroes. Increase the number of colors up to whatever you need to edit, then when you're done convert back down and import the edited palette, telling your image editor to match closest colors. THEN import the original palette and tell the editor to maintain color indexes. You should be able to re-import back into TLP cleanly.

That sounds like a lot of work Gid. I've never really liked inserting new graphics, but I just kind of did what worked best for me, which was take a screenshot in FCEU, give the screenshot to whoever will edit the image, then take that image and convert to BMP and insert BMP into the ROM. Usually the colors would be mixed up, which was an easy fix most of the time. I guess this is result of losing the palette data. Anyway, I generally use TLP, but I've been trying to get away from that and use YYCHR. I guess my main problem would be how to get an image that keeps the palette data intact.