Qué tal,
el orden en el que defines tus estilos es importante.
Debes definirlos en este orden para que funcionen correctamente:
a:link { color: #000000; text-decoration: none }
a:visited { color: #000000; text-decoration: none }
a:hover { color: #000000; text-decoration: underline }
a:active { color: #000000; text-decoration: none }
Prueba a ver si así se soluciona tu problema
