Firstly, you might want to consider using a wider "wrap". Very few users still use an 800x600 resolution and the lowest, most common denominator is 1024x768 res.
Assuming you want completely seperate divs rather than one header image as misson states, there are two ways you can do your layout..
First is the simplest and probably safest.. within your header div, just add (nest) two more divs (say id's headleft and headright), the first being float-left and the same width as your menu and the second being an "auto" width (which will fill to the outside of the wrap). This first option will be easy to change in the future if you want to return to a wide header div. You might also want to reconsider your div structure for "content"... as follows...
Code:
<div id="wrap"><div id="header">
<div id="headerleft">
<img src="whatever.jpg"/>
</div><!--end headerleft>
<div id="headerright">
Heading image/text
</div><!--end headerright-->
</div><!--end header-->
<div id="contentwrap">
<div id="menu">
menu links
</div><!--end menu-->
<div id="maincontent">
lots of text and stuff
</div><!--end maincontent-->
</div><!--end content-->
<div id="footer">bottom stuff</div><!--end footer--><!--yes this is extra-->
</div><!--end wrap-->
The second, would be to start with two column div's within the wrap, and then nest horizontal cells within each column.
Either way, all space below your menu is gonna be empty - which is why quite a few developers use a top menu bar.
Errr.. not sure why you need float-left on your wrap?