For anyone else that's interested..

In the CSEnvironment.properties file (in WebSphere\PortalServer\shared\app\config) the Domino hostname that is specified isn't resolving to a servers ip address.

Make sure the domain names specified for both of these resolve correctly to the server where the lookups are taking place.

CS_SERVER_DOMINO_DIRECTORY_1.hostname
CS_SERVER_DOMINO_DIRECTORY_1.custom_ldap_host

A quick change to the servers host file should test this, and shouldn't require a portal restart either.