Então eu descobri ...
1) Meu problema de conexão com o PuTTY foi devido ao fato de que eu estava tentando telnet para a porta LDAP (OpenLDAP ou Windows não gosta).
2) O problema com o script Python original era relacionado a permissões. Aparentemente, o usuário não ter permissões de leitura em algumas partes das bibliotecas LDAP faz com que o python-ldap retorne o ldap.SERVER_DOWN incorretamente.