Um simples ``` text-align:center;``` no seletor ```.menu ul``` deve resolver.

Então o CSS ficaria assim:


    .menu {position: fixed; top: 0; width: 100%;}
    /* ↓ eu só subistitui o margin por text-align:center na linha abaixo ↓ */
    .menu ul {font-size: 15px; text-align:center; }
    .menu ul li {display: inline; }
    .menu ul li a {margin: 0 auto;}


Exemplo:
### [**`FIDDLE`**][1]


  [1]: http://jsfiddle.net/h6UVS/