First of all, thanks to Mário Rufino and Luis Guido from Microsoft Portugal for providing support during the PCNS installation.
PCNS was installed in two domain controllers for the same domain in a large forest. Because none of the servers had the Schema Master role, the first time that the PASSWORD CHANGE NOTIFICATION SERVICE.MSI was executed was to update the schema in the Schema Master.
After the schema update we had to wait for the schema propagation to take place so we waited until the schema was updated thru all the domain controllers.
After that we just had to execute once more the PASSWORD CHANGE NOTIFICATION SERVICE.MSI in the two domain controllers that are going to receive the requests for password changes.