We ended up figuring it out after finding this link:
If your NetBIOS name is different from your domain name, at least Replicate Directory Changes permission is also needed on the cn=configuration container and you must enable NetBIOS domain names on the corresponding User Profile service application. For more information about enabling NetBIOS names on a User Profile service application, see Get-SPServiceApplication.
The UPA property NetBIOSDomainNamesEnabled is used to control whether the CNC partition is included in the AD MA or not. By default it is false (not enabled) and the CNC and associated run steps are not included in the AD MA configuration. If it is enabled, then the CNC partition and run steps are included.
When editing a connection, the flag is ignored. If the CNC was included in the AD MA when it was created, then it will continue to be included in the AD MA. If the CNC was not included when the AD MA was created then it will never be included in the AD MA.
To "enable" NetBIOS domain names once a connection is created requires the connection to be deleted and a new connection created with the flag turned on (set to 1 or true). For users that unintentionally import users with the flag turned off and later turn it on, this will delete all the users which had their SAMAccountNames incorrectly formed due to the NetBIOS domain name being incorrect.
How To: Enable import of NetBIOS Domain Names
Using the 2010 SharePoint Management Shell:
Get-SPServiceApplication <lists the Service Applications and their GUIDs>
$UPA = Get-SPServiceApplication –Id <GUID of User Profile Service Application>
Grant Replicate Directory Changes permission on a domain
Grant Replicate Directory Changes permission on the cn=configuration container
The one Clayton Cobb posted above.
Delete the exsiting connection and "Create New Connection" on "Synchronization Connections" page.
Perform "Start Profile Synchronization"