Ya lo entendí.
Pues hay dos opciones:
La primera es que en lugar de 100% le des un ancho de 790, creo que este es el ancho para una resolución de 800x600.
<table width="800">
Y la otra es, si quieres que cambie en función de la resolución del usuario, es decir, que no sea siempre de 800x600, tendrás que recurrir a Javascript.
Código:
<script>
function tamano(){
ancho=screen.width-35;
document.getElementById("cabecera").width=ancho;
}
</script>
</head>
<body onLoad="tamano()">
<table id="cabecera">
<tr><td>Menú de navegación</td></tr>
</table>
Prueba con distintos valores de lo que está en negrita, ya que puede variar según como tengas los márgenes y todo eso.
Un saludo.