Valid Email Address Being Rejected

When trying to register a new user using a valid email address (e.g. first_last@yahoo.co.uk). The email address is rejected with the error message:

The e-mail address first_last@yahoo.co.uk is not valid.

Clearly the email address 'first_last@yahoo.co.uk' is valid and is in use. I suspect that the problem might be because this email address contains an underscore.