SetPassword is very slow
I have been able to resolve this problem by opening the port 464 on the firewall which is the first attempt by the ADSI API to perform a CRL check on the network for user authentication.
http://www.pc-library.com/ports/tcp-udp-port/464/
Have you verified Active Directory replication between sites is functioning properly? Most attribute changes are passively queued for replication, but password changes are immediately replicated.