...estaba remirándome el asunto y veo que no hay asignado un width ni al elemento #menu ni al ul del menú. Ambos son elementos de bloque, por lo tanto abarcan todo el ancho que pueden ergo visualmente no pueden centrarse. Asígnale una anchura a uno de los dos elementos y le aplicas los márgenes derecho e izquierdo con los valores que te comentaba en mi mensaje anterior