Je suis pas sûr que ton tutoriel est à jour et est prévu pour windows 7. Tu as une raison de rester en lenny ?
Le message me semble assez clair, le client windows veut un nom de domaine bien configuré avec des enregistrements SRV (je connais mal windows). Le plus simple est d'installer un serveur dns bind pour ton réseau local et de te faire une zone propre.
Déjà openldap, c'est un peu galère à la base, alors si tu cumules avec du samba Tu as peut-être intérêt à te renseigner sur samba 4, qui comporte de grosses avancées pour windows (support active directory).
Et surtout, évite les vieilles versions de openldap, c'est déjà très difficile à débugger, si tu te prends des vieux bugs en plus...