Ciao,

Vuoi una cosa CSS3 o compatibile anche con IE7/8/9?

Se ti basta una CSS3 puoi usare le transition sull'elemento, ovviamente su IE non andranno e non vedrai la dissolvenza ma solo il cambio di colore immediato.
Ti faccio un esempio con il background, ma lo stesso principio vale per qualsiasi regola:

codice:
.classe-link {
background: #FFF;
transition: background .4s ease-in-out;
}
.classe-link:hover {
background: #000;
}
Ciao