Even if you have configured properly the cert7.db and you are able to browse successfully your AD by using the policy server Admin UI, you may have the following error when trying to authenticate when using AD with SSL as User Store :
Where DC.domain.com is the domain controller not the AD server.
This is due to the fact that all your Active Directory servers are not configured in SSL and some of them do not accept SSL connections. When the domain controller try to connect to one of the AD in SSL (636 port) it is not able to connect to some of them.
The solution is to disable the Enhanced LDAP Referrals on the policy server management console. You will then use only the AD servers defined in the list of the User Directory definition.