To test out a problem for a customer, I had to add a Windows 2000 server and MSMQ 2.0 to one of my domains. The installation of the Active Directory Integration portion failed as it could not contact the domain controller. The DC was definitely running but the "Message Queuing Downlevel Client Support" service, although set to Automatic, was failing to start which meant MSMQ was deaf to any 2.0 clients.

Event Type: Error
Event Source: MSMQ
Event Category: None
Event ID: 2035
Date:  02/11/2009
Time:  17:03:37
User:  N/A
Computer: DC4BTS
Description:
The Message Queuing service cannot start. The Active Directory interface cannot be initialized (Error: 0xc00e1001 in the downlevel client support service. See article 875530 at support.microsoft.com).

 The event description directs me to the following KB article:

875530 The installation of Microsoft Message Queuing 3.0 is not successful in a child domain when you use an Enterprise Administrator account

but unfortunately it was not relevant to my environment (only one domain in the forest).

First port of call was to see what the error code meant (in DSSVCERR.H): 

0xC00E1001 - MQDSSVC_ERROR_SETTING_NOT_FOUND

although that information wasn't startlingly useful as it doesn't say what setting it cannot find.

Next I had a look at the formatted output of the MSMQLOG.BIN error log and found something more revealing - "Failed to retrieve this site's information". So I was having site-specific problems.

Using the Active Directory Sites and Services snap-in, I could see that for some reason the domain controller's "MSMQ Settings" object was missing. Reinstalling MSMQ on the DC recreated the desired object and allowed Downlevel Client Support to start which in turn meant the Windows 2000 client was able to install properly.