Yeah; move your A:visited rule to right after the A:link rule; that will also let the A:active rule work.
I know, it seems to run counterintuitive (usually, the colors will be presented to the user in the order link, hover, active, visited, rather than link, visited, hover, active) but apparently that's how it works, given the CSS rules of how rules interact.