Help securing Exchange & Outlook!!!

Hello everyone! At our company we are using NT 4.0 (SP6), Exchange Server 5.5 (SP4) & Outlook 97, 2000 & XP as our clients. I have to setup message encryption and digital signing at the server and have managed to make it work for Outlook 97, but when it comes to Outlook 2000 & XP, when I try to subscribe the user for advanced security, the computer replies with: "The user name in the directory could not be accessed. Make sure you have a network connection to the Microsoft Exchange Server computer." Even though I'm logging on to the server directly (I have setup a test server and clients with a hub in the exact same configuration we use, isolated from the company's network, so that once I get it all straight I can go over to the production server and duplicate the steps and put it to work.) Can someone tell me what could be wrong here? Any ideas to try? Thanks a lot!