DUPLICATE_USERNAME Error During a Deployment and Using Change Set in Salesforce

To resolve the DUPLICATE_USERNAME,  the proposed method is to find duplicate users in the org.  Another option is to set duplicate management rules in the org so you don't get any duplicate users created even within the org's context. See Manage Duplicate Records for more information.

Usernames are shared across instances, but not across environments (production/sandbox). I.e. if a user account in a sandbox instance has username = a@b.c, this username cannot be used in any other sandbox instance (CS*), but it can be used in production instances (NA*, EU*, AP*)

Uniqueness is enforced during deployments when tests are run, so an insert call will fail if the username is already registered in another org in the same environment (production or sandbox). The resolution for this is to use a guaranteed unique username for tests. We recommend generating globally unique usernames, e.g. org Id + timestamp + random value, as the below code snippet shows:
 

public static User createTestUser(Id roleId, Id profID, String fName, String lName) {
    String orgId = UserInfo.getOrganizationId();
    String dateString = String.valueof(Datetime.now()).replace(' ','').replace(':','').replace('-','');
    Integer randomInt = Integer.valueOf(math.rint(math.random()*1000000));
    String uniqueName = orgId + dateString + randomInt;
    User tuser = new User(  firstname = fName,
                            lastName = lName,
                            email = uniqueName + '@test' + orgId + '.org',
                            Username = uniqueName + '@test' + orgId + '.org',
                            EmailEncodingKey = 'ISO-8859-1',
                            Alias = uniqueName.substring(18, 23),
                            TimeZoneSidKey = 'America/Los_Angeles',
                            LocaleSidKey = 'en_US',
                            LanguageLocaleKey = 'en_US',
                            ProfileId = profId,
                            UserRoleId = roleId);
    return tuser;
}

The proposed method is one of many different ways to find duplicate users in the org. Another one is to set duplicate management rules in the org so we don't get any duplicate users created even within the org's context.