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