Entonces lo tienes bien con el margin:0 auto (y quitando el margin-left de después, que supongo que lo has puesto para hacer pruebas). Lo que te está pasando es que el ul tiene un padding interior a la izquierda por defecto, que se lo añade el navegador si tú no lo reseteas. Ponle un padding:0 al ul, o mejor aún, usa un
reset para toda la web.