Hallo Markus.
Kann es sein, dass dein Link bereits "visited" ist?
Dann würde er sich diese Klasse schnappen.
Es geht mit a:visited:hover (neue Klasse).
Bin mir allerdings nicht sicher, inwiefern das Standard-konform ist...
try it
Oder schau mal unter http://selfhtml.teamone.de/css/eigenschaften/pseudoformate.htm#link_visited_hover_active_focus
da steht noch was von Reihenfolge der Pseudoformate. Vielleicht tuts auch das.
Grüße
Sascha