There is some great advice here already, but that won’t stop me from jumping in. Specifically I want to mention that the Web Content Accessibility Guidelines (WCAG) have some points on this that might be worth reading and will inform any errors you get from the tools listed above.
If you end up in a situation where legal compliance is the goal, then WCAG 2.0 is the de facto standard at Level AA (A is the simplest to achive, AAA the most difficult). I say de facto as that is where lawsuit settlements tend to target. I’ve listed a couple items that apply to the issue of color:
1.4.1: Use of Color (Level A)
“Color is not used as the only visual means of conveying information, indicating an action, prompting a response, or distinguishing a visual element.”
In short, error messages shouldn’t be just red, links should probably have underlines, don’t tell users to click the blue thing (though this relates as much to 1.3.3), etc.
1.4.3: Contrast (Level AA)
“The visual presentation of text and images of text has a contrast ratio of at least 4.5:1 […] Large-scale text and images of large-scale text have a contrast ratio of at least 3:1.”
Logos and strictly decorative (intentionally illegible) text are exempt. Large text is from ~18px up (there is open debate on px vs pt sizing). The contrast should also apply to text links and the surrounding text. And so on.