I couldn't of course just leave things as they were, so I did some digging. Everything I've read indicates that openldap, and by extension FDS, does not support UDP. As a result, an openldap server cannot respond to CLDAP queries such as those made by a Windows client. That doesn't always seem to have been the case. Earlier versions of openldap seem to have had a complile time option --enable-cldap. This option appears to have been dropped. I found a reference here to the to option no longer being available in version 2.1.22. Certainly in the configure script of the current 2.4.10 source code there is no mention of --enable-cldap.
I couldn't find any formal announcement, but perhaps the reason CLDAP support was dropped from openldap was because the protocol has been buried as an Internet standard. It's epitaph is recorded in RFC 3352.
From a practical point of view, all this means is that you have to treat a Samba server - even one with an LDAP backend - as a NT 4.0 server and connect to it via NetBIOS. If you specify a DNS name, Windows thinks you are connecting to Active Directory. This is made clear by the subtly different error message you get on Vista:
Don't think this is the end of CLDAP, however. It is obviously still being used by Active Directory, and if it is still being used by Active Directory, it will have to be supported by Samba 4.0.