Hey there jbteta, I have a solution for you.
First, paste in your BMP file onto the first layer, then make a new layer and paste your GIF onto that. Erase the bits which need transparency by using something like, say, the magic wand tool.
Also, you could try renaming the .gif to .png, and try paste it in then; however, I think the issue may be that you weren't using layers - correct me if I'm wrong.
Hope this helps!