Changing the validation applied to sitecore usernames is relatively straightforward, search your web.config file for the AccountNameValidation setting, this allows you to specify a Regex to use when validating new usernames.

The following example will allow any username:

<setting name="AccountNameValidation" value=".*" />