This answer is from StackOverflow and includes comments
Being part of a domain is a pre-cursor for installing MSMQ in AD-integrated mode. It doesn't guarantee MSMQ IS installed in AD-integrated mode. MSMQ will install in workgroup mode if:
AD integration was not selected as a setup option
AD integration was selected but failed to initialise; check event logs
Yes, the workgroup name is confusing in a domain member situation.
I checked the logs and found that MSMQ was detecting a previous MSMQ configuration conflicted with it working with AD. I had installed MSMQ, and later enabled the AD integration. I completely uninstalled MSMQ, and then reinstalled it with everything (AD integration included), and I stopped getting the error.
Your comment describes the answer that worked for me: not only did I have to add the extra MSMQ components, I had to uninstall MSMQ completely first to get it to work properly.
Deleting the MSMQ object in AD first should do to the trick.