I had the same problem. Its not practical in zen cart to use one huge logo across the top. As each person views it in different resolution. What i had to do was to crop my logo to a 130px by 90px and then make a 250px by 13px of the background and set it to repeat across the back.
if you look at my logo www.edealbase.co.uk/index.php the bit which says edealbase is a small jpg. All the blue background you see is a 250px by 13px image repeated (which would be the header img) and the white writing is the tagline.
its a bit annoying but basically the only way to fix your problem is to remake your logo.
PHP Code:
#logoWrapper{
background-image: url(../images/logo_tile_back.jpg);
background-repeat: repeat-x;
height:250px;
}
The above bit is in the stylesheet.css. logo_tile_back.jpg is the 13 x 250 px slice of my logo i uploaded and have it repeated.
Sorry if this is hard to understand, hope you get the general idea though!