No cambia de Color

[kseso?]

No necesariamente, pero nada se lo impide.
Es más, si está dando un estilo (apariencia) propia a sus enlaces/botones, ¿por qué no hacerlo también con ese pseudo-estado?
Puede, tranquilamente, definirlo conjuntamente con otro:

Código CSS:

a:visited, a:hover {}