This line is causing your problems:
#menu li a {
color: black;
display:block;
text-decoration:none;
}
This makes any and all links that are child of a list item display as block, which causes the vertical stacking that you're seeing.
Change that selector to #menu li > a
and you're good to go. View it on JSFiddle. What this does is only apply the styling to links that are direct children of list items.