Amigos.
Les cuento que solucione el problema mediante este codigo:
Código HTML:
#menu{
width:718px;
height:42px;
border:1px solid #FFF;
background-color:#0e283f;
padding:0;
margin:0 auto;
margin-top:-1px;
position:fixed;
z-index:100;
left:50%;
margin-left:-361px;
}
El secreto es este: left:50%; margin-left:-361px;
Lo unico que no funciona para IE6.