Hi.

That is happening (most likely) because Firefox is not storing your browsing history for long, or at all. Go into Tools > Options > Privacy and make sure the configurations are set as you want them to be. If they are, it's likely you have some security software that's erasing your Firefox's history (and possible other browsers' if you have them installed). The most likely suspects are antiviruses, firewalls and security suites, but clean-up utilities like CCleaner are also capable of cleaning Firefox's browsing history and other personal data. Make sure you don't have them configured to do so.

I should remind you, however, that some sites (they are rare, though) don't have their links change color when visited. That happens only when their authors deliberately make them not change the colors. You can force websites to use a color scheme of your choice by going into Tools > Options > Content > Colors... and unticking "Allow pages to choose their own colors". You can also configure the color scheme in that screen.

I hope this helps.

Thanks to Morbus, I was able to restore the color change for Visited Links. Go to Options, Privacy, and uncheck the "start...Firefox as a private browsing session". So far the loss of the "private browsing session" functionality is not a problem.