Included is a screen capture to show the problem I'm having. I started rendering my naval units with an off blue background, the same as Wyrmshadow uses. I replace the original magenta with it, but I get this problem ingame. Any ideas ? Thanks.

I haven't done anything with units but.. isn't pallete position just as important as the color used?

It looks like it's in the shadow/smoke lines in the palette.

Make sure that the color that is set as the fully transparent color is only on the palette once (usually the last or the first color :D ) It may be that the color you are using for the background is actually one of the shadow colors... When you paste an image onto a storyboard it will match up the colors in the image to the first color that matches it on the palette... So you might have that same blue color somewhere else in the shadow/smoke section of the palette.
Position is really more important than actual color. I could make the civ-specific colors whatever I want and the game would still turn them blue or pink or red or whatever. Same goes for the shadow and smoke colors...