Was it interlaced? I only noticed it was 360+k, in other words three times larger by itself than I'd allow a normal page on a website to be TOTAL.
Here's what I came up with:
Which works all the way back to IE 5.5 - BUT
There are a bunch of design elements in there I wouldn't even be DOING - like the uber-spaced side menu next to the banner image, or the giant honking banner image pushing the content clear off the screens at lower resolution - of course I wouldn't be doing a fixed width layout EITHER so...
I did add back in two wrapping div mostly for clearing behaviors but also because of that disastrous idea for a sidebar next to the banner, I put the background on that.
I ditched the idea of that slashed background being different on all your corners since that would NEVER line up and looked like a rendering error, and instead just put a wrapper behind the content, padded it, and tiled a single slash pattern on it. Much simpler, much more uniform.
The menu only uses CSS for IE7/newer and alternative browsers, and throw csshover3.htc at IE6 to make it work there. To get the depth sorting to work right in IE6 I had to throw some z-indexes in there, and fix the width of the flyouts since you end up in float hell there. (IE does NOT like turning off float behaviors and will give you back the forced side padding on a UL otherwise)
There's a whole bunch of clear:both since with the flyouts you can't use overflow:hidden to wrap the floats; thankfully float:left; width:100%; gives you much the same behavior.
The menu, hover states and bottom border I condensed into a SINGLE image file.
Because you need to absolute position the flyouts on the main menu (and can't trust EM thanks to FF being a retard about rounding off values) and because there's a fixed height image behind the menus - and because that side menu needs to stay the same height as the image it's next to we're forced to use PX fonts on them. The footer on the other hand has no such extra elements, so I kept that the default font size and positioned the roundedBorders image bottom right - so it can expand in height without problems.
With the big banner image I upped the encoding to 15% which really didn't add any visible at normal zoom artifacting due to how 'busy' the original picture was. I'd seriously consider axing that as a waste of bandwidth and space. The design is chewing up almost 700 pixels height before you get to ACTUAL content - that's bad.
Also I padded the top and bottom so that the rounded corners weren't flush
Between the re-encodings and code reductions the whole thing is a fraction the size of your original, and goes from 390k in ten images to 104k in 4 images. The reduction in the number of files reduces the total to six handshakes with the server, under the 8 simultaneous connect limit in most browsers!
Hope this helps.
P.S. You'll notice I axed the 'welcome' heading. I hate that crap. Doesn't add anything to the user experience, doesn't do anything to help with SEO, usually doesn't add any meaningful structure - it's a wasted element and way too 'friendly' for a business.