Oh boy, this took hours of pulling my hair out trying to determine why a:visited was not working on a new theme when viewing in Firefox but was totally fine in IE. Here’s a tip:
Make sure your Firefox isn’t set to “0” days in Tools => Options => Privacy
If it is, Firefox ignores the a:visited styles.
Found the answer on thescripts.com.
Ridiculous amounts of time were wasted because of that setting. Who knew.
If that isn’t it, make sure the link order in the CSS file is: