Prueba cambiando este width:
div.menu {
width:150px;
background:#FF0000;
}
Para
div.menu {
width:auto;
background:#FF0000;
}
Con eso, el width efectivamente tomara toda la pantalla, pero los <ul>'s deberian salir uno tras otro.
Ya luego solo es de ir calculando el width necesario.