forse non ho capito cosa vuoi ottenere, scusa.

ma nell'ultimo CSS che hai postato l'hover va ad agire unicamente sulla sottolineatura

a:hover
{
text-decoration: underline
}
per fare in modo che abbia un'incidenza anche sul colore dovresti aggiungergli, come nel primo css postato

color:#003366;