Would love some help on CSS/Tables/Hotspot

I am doing a website for a client, and I am using CSS-based template that has worked well for me through multiple sites.  it is a standard 3-column layout with header, submenu stripe (horizontal navigation bar) and a stripe in the footer for a secondary navigation bar. 

This client wants both a search bar in the top RH corner and buttons on the bottom RH corner of the header (which sits in the CSS as a background image).  I have been playing with how to accomplish this.  My first thought was to create a table that spans the entire height of the header, but that seems to push down the submenu.  My second thought was to follow A List Apart's Night of the Image map, but I am having trouble getting it to float in the wrapper/header divs.

My html

My css

I would dearly love some help.  I have used the Night of the Image map technique in previous websites before, but never in this particular fashion, so I don't know if it's the approach or if it's my error.  Same with tables.  I generally hate throwing in tables to my CSS work, but I'm not sure what else to do!

Thank you in advance!