A GIF image is color-indexed, each color is a one-byte index in a 256-colors (max) "color map".
When you edit such a file in Gimp, Gimp keeps it as color-indexed, and will coerce any color you use into the closest one in the color map (Gimp will not alter the color map on its own). This also applies to images you import in the project (File>Open as ...
The problem is caused because all GIFs use Indexed colour. It has nothing to do with GIMP really. The problem is with the image format itself, and the way that colours are stored in it. Anyway it's easy enough to fix.
Open the first GIF image
Do Image > Mode > RGB - this will solve the colour problems when importing the GIF in the next step
The problem is that each of the original elements had its own palette.
On the combined GIF, the second clip is using the palette of the first one.
One option is to convert the files to 24 bits and reconvert it down to an indexed palette, taking now into account all the colors of the sequence. You will have fewer colors because some of the colors will not ...
I found this thread to try and find the answer myself, and have decided to use LiceCap - an openSource screen capture gif creator - I just used it to create an 8.5MB file from a 16 second video clip, though I'm sure if I tweaked the settings and made it smaller could have saved more space