Hello crashprojects,
Have you inspected your website with a useful too such as Firebug (with Firefox)? These are really useful tools for seeing what styles are being overridden or not applied, occasionally an inherited style may overrule another style (that we would like). You can overrule styles with the !important instruction which says to the browser - this is the style I'd like to apply. So you could try something like adding this into your stylesheet:
.sf-menu a:visited {color: #enteryourhexhere !important;}
If we have a link to your website we can then view your stylesheet and see what may be causing the issue with your visited links. I assume you've copied the Divs and Class's from Helga's great work on Thematic menus demystified, see number 6 "Styling the Beast" - http://themeshaper.com/forums/topic/thematic-menus-demystified-1. Apply the visited styling to all the logical levels you need after looking at where Helga outlines the top level styling, 1st level, etc, etc.
Also, are you using a child theme, as normally the styles you enter this stylesheet should overrule the parent theme (thematic) - although there are occasions where this is not the case. If you're not using a child theme, I'd recommend you do for ease of customisation and future upgrades.
Someone else may have a better suggestion but that's how I'd approach this problem :)