First of all, when you change any colors on your page (background, text, link, hover link, active link, visited link), then you should change them all, in case some of your page's visitors have overridden the default browser colors.
Second of all, since visited links are still links, I think that their colors should not differ much from the regular links' colors. Purple (default for visited) vs. Blue (default for links) are close together on the color triangle. As Awesh mentioned, the nature of the difference which seems intuitive to new vs. old (visited) link is a fresher color vs. duller color e.g. less bright or less saturated.
Third of all, make sure all your text colors have high enough contrast from the background. E.g. if the background is white, make all the text colors at least as dark as 50% grey and if your background is black, make all the text colors at least as bright as 50% grey, or better yet, check out the W3C guidelines or explanation in this answer.
Forth of all, if you do alter the default colors, consider offering an alternative theme, in case the theme you choose is not comfortable for some visitors (see this answer for more info).
Reference image, the color triangle: