¿Has probado a colocar el fondo como fondo:
Código css:
Ver original#menu ul li a {display: block; background: url(tuimagen.ext);/*define el tamaño si fuera necesario*/}
#menu ul li a:hover {background: url(tuimagen2.ext);}
De todas formas, tienes una estupenda colección de menús sólo css en este foro obra de
Mikmoro de probada funcionalidad con múltiples navegadores (incluido ie6)
Un saludo