Hola!
sí, efectivamente, deberías usar float: left; en el logo y float:right; en el #menu, pero debes corregir los botones, no puedes usar divs para cada botón.
Los menues deben estar organizados en listas
Código HTML:
<div id="menu">
<ul>
<li><a class="bt_galeria" href="#galeria.html">Galeria</a></li>
<li><a class="bt_imagen" href="#contacto.html">Imagen</a></li>
</ul>
</div>
y después declaras las propiedades
Código:
#menu {}
#menu ul {}
#menu ul li{}
#menu ul li a{}
#menu ul li a:hover{}
a.bt_galeria {}
a.bt_imagen {}
Y el "palito" lo haces con un border-right en .bt_galeria{}
Otra cosa.. ese menu está hecho con imágenes... te parece necesario? no es una arial o algo muy parecido?
Trata de simplificar y saldrás beneficiado.
Saludos!