Save as Web, and save it as as little colors as you can. I hope this helps. Thats how I remove the white border when I have that problem. Other wise try adding a black glow around your image which might help a little to take away the white stuff..
when saving a transparent image for web you will need to define a color to blend transparent pixels against. you pick this color when the "save for web" window appears. look for "matte" to the right. choose "other" and then define your color. in your case after viewing your web site i would say you need some kind of dark red.
making transparent images on multi-colored backgrounds look good is difficult, but experiment until you find something that works for you.
You could, probably, try using a PNG instead of the GIF. The file-size is going to be bigger, but they seem to handle transparency better (from what I've heard).
Another option could be to just add the logo design to the background image. This'll save you from having to worry about transparency and others from having to download multiple files to see the entire header image.
Linear Mode
