Go into your template image folder and see what the logo.gif looks like in a image editor (Photoshop).
Create a logo in a size similar to the original 300 x 75 etc and upload it.
Then you can see if you need an even larger one.
Just uploading text or logo with a transparent background won't suffice because a visitor resizing your window could make the logo.gif run off the header unless you add a minimum width value to your CSS page.
body
{
min-width: 800px;
}



