It certainly appears that something changed with the certificates, but if this is the case, whatever changed must have been automatically propagated to Domain joined Windows systems without human intervention (is this possible?)
Yes, this coud be possible. Windows systems don't use LDAP+SSL to securely connect to Active Directory. They use GSS-SPNEGO, which usually means they end up using GSSAPI with Kerberos tickets, unless they are very old Windows systems.
Kerberos tickets are not related to X.509v3 certificates, so that's why even if your root CA and DC certificates are rotated, the Windows systems can talk to AD without problem (but note that AD can push lots of stuff to Windows clients silently, especially credentials to access AD-related services and resources, and things related to Enterprise CAs managed through Windows Certificate Services or whatever it's called nowadays).
@Ken do you recommend a different method and output for conversion - any examples on how to do this?
I'm not Ken, but I hope you don't mind me answering the question 
PEM is the right format if you are using OpenLDAP's libraries (which is what PHP uses unless you compile it yourself specifying a different supported library). It's the format OpenLDAP's libraries expect.
Regarding LDAPs do you think I should include the private key and intermediary certificates?
You don't need the private key to verify the DC certificate at all (in fact you SHOULDN'T copy the private key anywhere, except for disaster recovery purposes). Even more surprisingly, you don't even need a copy of the DC certificate! You just need the public key (which is part of the certificate itself) for the CA. Or if you are using intermediate CAs, the certificates of all the CAs in the trust chain starting from the root CA and up to the CA signing the DC certificate (this is what some people call the "CA certificate bundle").
When connecting to the DC via SSL, the DC will send the certificate back to the connecting system as part of the SSL handshake (see http://www.moserware.com/2009/06/first-few-milliseconds-of-https.html for all the gory details). In order to verify the authenticity of the certificate (in addition to temporal validity, the name of the remote system, etc.) you'll need to check the digital signature of the certificate. And for that, you'll use the certificate of the CA issuing the DC's certificate (and the upper CA issuing that CA's certificate, and so on, up to the root CA). And that CA's certificate must be valid. Which means, among other things, it shouldn't have expired.
So you need to make sure that the COPY of the CA's certificate that you copied to your Moodle server has not expired. Which means you should check when your CA's certificate is going to be renewed (which happens on your Windows Certificates Server, and might happen way before it will expire) and then export and copy the new CA's certificate to your Moodle server. I would keep the old CA's certificate around until it expires, because some certificates could be using the new CA's cert and some others the old CA's cert.
Yes, it's a bit complicated, with lots of moving parts that can break down when you don't expect them 
Saludos.
Iñaki.
