1. The logo uses more than 256 colors therefore a transparent gif is out of the question.
My photoshop can export to a 256 color gif...

2. The logo itself will change on occasion. What you have described to me is fine if the logo itself is static and the only the background behind the logo changes.
All the more reason to seperate it - then you only need change one image and not the dozen that you are talking about