A lo mejor siguiendo el aporte de alexk lo puedas solucionar. Bien utilizando alguna propiedad css3 (
1 2) o bien colocando una imagen para:
#menu li a{background-image:url(imagenUno.png);}
y otra para:
#menu li a:hover{background-image:url(imagenDos.gif);}
Saludos!
