I was getting this message on a multi site install that I was working on:

Usernames can only contain lowercase letters (a-z) and numbers.

I haven’t dug into this yet, it seems like this popped up in WP 4.4. Here is how I have gotten around it:

function amr_wpmu_validate_user_signup( $userinfo ) {
	if ( array_key_exists( 'errors', $userinfo ) ) {
		unset( $userinfo['errors'] );
	};
	return $userinfo;
}
add_filter( 'wpmu_validate_user_signup', 'amr_wpmu_validate_user_signup', 999 );