I managed to work out the answer today.
I added the following line into /etc/ldap/ldap.conf
TLS_REQCERT never
After this I was able to connect but was still getting the error message:
Server Unwilling to Perform
This was because I was trying to set the password plain text like:
$ldaprecord["unicodepwd"] = 'MyPassword1234'
You need to encode it first so once I change my code to this it works:
## Create Unicode password
## Assumes that given password is in UTF-8 encoding!
## Adjust it to the actual encoding of the password
$pwdtxt = "MyPassword1234";
$newPassword = '"' . $pwdtxt . '"';
$newPass = iconv( 'UTF-8', 'UTF-16LE', $newPassword );
$ldaprecord["unicodepwd"] = $newPassw;
Hope this helps someone!