No entiendo la distribucion que usas ni como estas usando las propiedades del css... Pero bueno, yo usaria algo similar a esto:
Código CSS:
Ver original#logo {
background-image: url(tu imagen);
width: el ancho que sea;
height: el alto que sea;
}
nav ul {
float: left;
margin-left: el ancho del div anterior;
}
nav ul li {
las propiedades que sean necesarias.
}
No soy muy ducho en la nueva estructura del HTML5 pero juraria que el nav es un elemento independiente al header por regla general. Tampoco se como va el control de flujo en HTML5 por lo que no se donde seria más correcto usar la limpieza de flujo tras el float, quizas alguien mas entendiedo en esta nueva version pueda matizar mas sobre esto.