Just a stab in the dark, it sounds as if the logo is in a container with a set width.
Suggestions:
Viewsource and see if there are set dimensions on the container holding the logo.
or
If you use Firefox use the Web Developer Toolbar, to identify the block, css and image properties to find out which one is causing the conflict.
Good Luck
Carl