Image.paste with images with different palettes...

[Tracubik]

Hi all!
I'm trying to create a map generator for c64's games

it's a simple script and it work properly, but i've problem if i try to 
modify images before creating the map.

what i do is:
- take a 8 bit screenshoot with VICE emulator in gif or bmp format
- open shutter (screenshoot edit tool under linux) to modify the 
screenshoot (i.e. insert note of sensible part of the screenshoot)
- save the modified screenshot
saving the screenshoot modify the palette of the 8 bit image
every modified screenshoot have different palette
trying to paste the modified screenshots in a new image (Image.paste) 
result in a map with wrong colors.

Converting all in RGB solve a bit but result in a "grainy" image

any hints?
maybe using GIMP and setting it properly could help, but shutter have a 
so nice arrow tools...