This post is intended for those stumbling upon this exact error. It’s not particular hard to troubleshoot if you watch the System Event log on the FIM Synchronization Server. There’s no AD integrated Certificate Authority in the lab environment where I’m implementing the enforcement of password history. Therefore trusting the root CA, which issued the certificate for the DC, has to be done manually. If you don’t add the certificate of the root CA to the trusted root certificates on the FIM Synchronization Server, the following errors will be shown:

In the Application Log: FIMSynchronizationService Event ID 6328

The server encountered an error while attempting to perform a set/change  password operation.
 
"BAIL: MMS(2528): dnutils.cpp(1329): 0x800700b7 (Cannot create a file when that file already exists.): Cannot add partition DC=DomainDnsZones,DC=contoso,DC=com to the list because it already exists at position 15
BAIL: MMS(2528): dnutils.cpp(1329): 0x800700b7 (Cannot create a file when that file already exists.): Cannot add partition DC=ForestDnsZones,DC=contoso,DC=com to the list because it already exists at position 16
ERR: MMS(2528): utils.cpp(907): Failed getting registry value 'ADMADoNormalization', 0x2
BAIL: MMS(2528): utils.cpp(908): 0x80070002 (The system cannot find the file specified.): Win32 API failure: 2
BAIL: MMS(2528): utils.cpp(963): 0x80070002 (The system cannot find the file specified.)
ERR: MMS(2528): session.cpp(1502): ldap_connect (timeout= secs and  usecs) failed
BAIL: MMS(2528): session.cpp(1504): 0x8007003a (The specified server cannot perform the requested operation.)
BAIL: MMS(2528): admaexport.cpp(2683): 0x80231109 (Cannot connect to the server you have specified.)
ERR: MMS(2528): admaexport.cpp(3160): Unable to set the password.
BAIL: MMS(2528): admaexport.cpp(3168): 0x80231109 (Cannot connect to the server you have specified.)
ERR: MMS(2528): ma.cpp(9099): ExportPasswordSet failed with 0x80231109
Forefront Identity Manager 4.0.3561.2"

Graphical:

And in the System Log: Schannel Event Id 36882

The certificate received from the remote server was issued by an untrusted certificate authority. Because of this, none of the data contained in the certificate can be validated. The SSL connection request has failed. The attached data contains the server certificate.