YEP! Changing the LDAP SSL certificate requirements from "required" to uh.. not.. made the error go away on our domain.
Computer configuration - Policies - Windows Settings - Security Settings - Local Policies/Security Options - Domain Controller: LDAP server signing requirements (None/Require signing/Undefined[which is the same as None])
A quick google search brought up this likewise discussion, where a member of likewise states that they don't support ldaps.
The ticket for me was the "LDAP error code: 8 (Strong(er) authentication required)" line in /host/messages. No verbose logging was required to get to the root of the problem.
Good enough for me and my crew.