The issue is due to the improper status of avdsad and avdsglobalcatalog services on the Cisco Unity server or due to improper installation on Cisco Unity.
To resolve this issue, determine if avdsad and avdsglobalcatalog services are running on the Cisco Unity server under the Services window. If not, start the services and re-run the Message Store Configuration Wizard (MSCW). If you do not have these services under the Services window in Cisco Unity, register them by issuing the avdsad -service and avdsglobalcatalog -service command from the command prompt on Cisco Unity server.
Run service configuration tools from the Cisco Unity Tools Depot to make sure that all the services are logged in with proper accounts.For more information, refer to Utility Updates in the Cisco Unity Tools Depot.
If this does not resolve the issue, re-install the unity server.For more information on Cisco Unity Installation, refer your specific Cisco Unity Installation guide from this list of Install and Upgrade Guides. Also, refer the document Unity Failover Error Messages to troubleshoot Cisco Uity Failover issues.