I can see that in IE 7, which is a tad better than the older versions. I couldn't see anything wrong with your header code, seeing how you removed the tagline wrapper to properly utilize a full length header banner in place of the mini logo.
So... I could suggest a method that may or may not work. It will require modifying your current stylesheet.css and tpl_header.php. Make some desktop backups of the stated files, in case of trouble.
In your stylesheet.css, find;
Code:
#logo, .centerBoxContents, .specialsListBoxContents, .categoryListBoxContents, .centerBoxContentsAlsoPurch, .attribImg {
float: left;
}
Omit the logo selector(in red). You don't need that in your case and if you go to the second step and not omit this, your layout will break as your header banner/logo will slingshot your layout to the right.
So... now, open your tpl_header.php and scroll down to this;
Code:
<br class="clearBoth">
<!--eof-branding display-->
You can now safely omit that break.
As far as IE6 and prior versions, I don't know if this will totally remedy the problem as those browsers are so buggy as it is. Microsoft may think they own the Internet, but their browsers remain sucky.