You can try to override the strings or theme the message as has been mentioned already. Another option is to override the validation function for that form or that field, and raise the error yourself with the message you want.
You can use hook_form_alter in various ways. You could simply replace the #validate function on the submit button on the form, and thus provide your own validation function. In that function call form_set_error to raise the validation problems.
If you want to keep the core validation for most fields and just override the validation for one field you could set #limit_validation_errors to the submit button. This allows you to define which part of the form should have errors validated (and thus, which ones should not). You'll still want to add your own validation function for the form elements you've just ignored - so add it to the functions in the #validate of the submit button.