Only thing I can think of at the moment is try setting the margin and padding to 0. I am thinking that changing the menu to a block is effecting the position. Did you try removing the display setting and place all images for the menu on a single line?
Actually I am surprised you don't have bigger gap due to the warcraft logo. With one div on top of the the div the floats should not be necessary. The floats are to allow the divs to move up to the side of another div.
Without the float you can use a negitive value for your margin to push the lower div up tighter to the div above it.
Hope this helps, good luck.