GIFs have a very limited color palette. You need to do your cut and pasting within an application that will allow you to convert the images to true-color. This way combining the two together will not alter their colors. Then you can convert the combined image back to Indexed color if you want it to be a GIF or just leave it as true-color and save it as a JPG or PNG.