Si pones ese código (sin width), la opción del menú por ejemplo "Inicio" no cambia el fondo hasta que te acercas a la palabra en sí, pero si dejas el width, cambia en el momento que entras el el recuadro por cualquier parte, por ejemplo la esquina izquierda.
Hablo en IE6. Si no te ocurre eso puede que estés usando el Múltiple IE, que tienes errores de dibujado como ese en IE6.
Otra cosa:
Cita: #menu a:hover {background-color: #e9eada;
color: #333;
line-height: 32px;
}
Has quitado el borde del original. La reducción del line-height a 32px es debido al borde.