There's a new KB article out for MSMQ 4.0:

935498 A Message Queuing 4.0-based server runs in Workgroup mode after you install the Message Queuing Active Directory Domain Services Integration feature

This problem may take you by surprise as it's not how previous versions worked.

In the past a reinstallation of MSMQ in Active Directory Integrated Mode would go as follows:

1. MSMQ installed first time
2. MSMQ object is created under the computer object in AD
3. MSMQ uninstalled
4. MSMQ object is deleted from AD
5. MSMQ installed second time
6. MSMQ object is re-created (although with a different GUID) under the computer object in AD

With MSMQ 4.0, the object deletion step is missing so you will instead see:

1. MSMQ installed first time
2. MSMQ object is created under the computer object in AD
3. MSMQ uninstalled
4. MSMQ installed second time
5. MSMQ object for previous installtion still exists so setup installed MSMQ in workgroup mode

The workaround is to manually delete the MSMQ object after uninstalling. Not very elegant, I agree.