Gifs don't actually support alpha channels; they actually use a pretty weird way to deal with transparency. Here's a thread on it.
Basically, since it's a gif, you can just use the color key on the color where it's supposed to be transparent and you shouldn't have a problem. However, GIF is a pretty terrible type of file format to use for video, why not save it out as a Photoshop file (which does support Alpha channels with VARYING levels of opacity)?
- The Great Szalam
(The 'Great' stands for 'Not So Great, in fact, Extremely Humble')
No trees were harmed in the creation of this message, but several thousand electrons were mildly inconvenienced.