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 featureThis 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:
With MSMQ 4.0, the object deletion step is missing so you will instead see:
The workaround is to manually delete the MSMQ object after uninstalling. Not very elegant, I agree.