On some sites it is necessary to enable the option to override the color of visited links, but even that may not work due the css, element style and the structure of the page.

Technically speaking, this plugin is working if the link is added to the browsers history, the rest of the functionality is dependent on firefox itself.

Without knowing what site/page this is occurring on it's difficult to provide any more help.