The mozilla foundation may have changed the default setting for visited links.
To fix the problem, type 'about:config' (without the single quotes) in Firefox's address field. You may get a warning that what you're doing may be dangerous. Continue.
Type 'visited_links' in the filter field. You should get one entry that says:
layout.css.visited_links_enabled | ('default' or 'user set') | boolean | false
Double click the line and it should toggle the 'false' to 'true' and then leave that page.
Now the links that you visit will change color properly.