#menu {margin-left:auto; margin-right:auto}

denedinmi?

olmaz ise margin-left: herhangi bir değer girip manual olarak yapman gerekicek tabi buda bazı tarayıcı sorunlarına neden olabilir.

Edit: kusura bakma şimdi fark ettim denemissin ama menunun genişliği ana containera eşit olduğu için menunun herhangi bir ortalama olanağı yok.
O yüzden menunun genişlik değerini düşürüp sadece yukarıda verdiğim kodları kullanırsan büyük ihtimal ortalanacaktır.

Tekrar edit: Denedim ve gayet güzel çalışıyor şu şekilde tasarlarsan sorun çözülecektir.

<style>
ul {list-style-type:none; width:655px;border:1px solid red; margin-right:auto; margin-left:auto; display:table}
li {float:left; margin:15px}
#container {border:1px solid green;}
</style>
<div id="container">
<ul>
<li>sdfasfsa</li><li>sdfasfsa</li><li>sdfasfsa</li><li>sdfasfsa</li><li>sdfasfsa</li><li>sdfasfsa</li><li>sdfasfsa</li>
</ul>
</div>