Problema con rollover

[exxqizofrenicoo]

la primera cosa que veo es que repites las cosas.
en css se heredan los atributos.

ul.menu li
{
position:relative;
margin-bottom: 4px;
width:110px;
padding:2px;
background-image:url(../Imagenes/Fondos/fd_menurojo1.gif);
display:block;

}
ul.menu:hover li
{
background-image:url(../Imagenes/Fondos/fd_menuazul1.gif);
}

no es necesario escribir lo mismo en este caso.

dejanos el html tambien asi lo pruebo porque nose como tienes creada las listas.
o mejor si lo tienes alojado en algun lado dejanosla url

saludos