Here, I made something for you It's not perfect cos you didn't sent me any editable version of your logo so I had to use your current one as bitmap.
I made you a new header background cos I thought it would look better with the new logo. Logo is transparent PNG so to avoid any problems with IE6 visit this site http://www.twinhelix.com/css/iepngfix/. To see how it would look like I made you a demo.png.
Note! Background image is 5px in width, to use it just set "repeat-x" in your CSS.
If you like what I made please donate some credits or add +rep
My main problems are with the inconsistent colour scheme. Light blue font is difficult to read on light backgrounds ... and it seems like a wrong colour choice with your red header image. Consider changing your link colour to red to match the header or change the red in the header to dark blue and darken the blue in the links.
Another inconsistency are the bright green tabs... change those to grey or red (if you decide to stick with the red header) or blue (if you go with blue)