I've done it many times, so I'll describe the steps in case you're doing anything different:

* Mask the image and fill the background with a colour near to the page colour the image is going to sit in (makes colour fringing less noticeable). If it won't fill, invert the mask and try again.

* Once filled, remove the mask.

* Convert the image mode to 'Paletted (8-bit)', Optimised 256 colours (reduce the number of colours if you want to keep the file size small). Click OK.

* Go to: 'File > Save As' and choose 'GIF - Compuserve Bitmap' from the 'File of types' drop-down box.

* Type a file name and click Save. The GIF Export dialogue box will appear.

* Click the Image colour button.

* Click the eyedropper button and take the eyedropper to the left-hand image.

* Hold the eyedropper over the part to be transparent and click the mouse-button.

* Click OK.

You've probably done most of that already but maybe something there will help.