Userscripts.org

This works in conjunction with your history settings, and will work exactly the same as if youtube had not masked the "visited links" by using their own stylesheet. If it's not working for you, first check your browser history settings. I notice that you have also downloaded other youtube scripts. More than likely, one of those scripts is in conflict with this one and has probably overwritten the style created by YouTubed Already. Solution: first disable all of your other youtube scripts so you can see what this one actually does. Then, one by one re-enable the other youtube scripts until YouTubedAlready stops working. When you discover the conflicting script, you can either disable it or check through the script to see if it tries to write a style for ".video-entry a:visited". You may be able to solve the problem by adding the first line of YouTubed Already to the BOTTOM of the script which is in conflict.

NOTE: This script only changes the color of the link text (currently to brown) in "related videos" and most of the site. Only in the "search results" does it also change the background to gray. If that's what you're looking for in related vids, it does not do that there, since there is no div tag for that there.