¿Tienes firebug instalado? puede que haya otra regla de estilo que esté sobreescribiendo el color del link. En todo caso, intenta utilizar:
Código HTML:
#menu li a:hover,
#menu li a:active
{
color:#000 !important;
}
Échale un vistazo a esto:
http://www.desarrolloweb.com/articulos/declaracion-important-css.html