Reset Firefox visited links (purple→blue)

• In Firefox click on the Menu button (upper right corner)
• Choose History
• Select Clear Recent History
• Here it gives you the choice of: Last Hour, Last Two Hours, Last Four Hours, Today, Everything. Choose whichever you prefer.
• At the bottom of that Window there are check boxes for a number of things that can be cleared. If you only want to reset the purple links back to blue, just uncheck everything except Browsing & Download History
• Click Clear Now at the bottom and you're done. Now previously visited links will show as blue again.

Edit: I would like to add that this solution does not meet one provision in OP's original question/request; namely, it does not keep the URL autocomplete data. The purple visited links are tied directly to the browser history, so by clearing that it does reset the links back to blue as if they were not visited. Unfortunately it also clears the same history that the URL autocomplete is tied to.

Solution

Tools > Options > Privacy > Firefox will: "Use custom settings for history" Deselect: [ ] "Always use Private Browsing mode"

You can also check the layout.css.visited_links_enabled pref on the about:config page and make sure it has the default value. You can open the about:config page via the location/address bar. You can accept the warning and click "I'll be careful" to continue.