Make sure to set the clocks for MSMQ
If you are using public queues and addressing them with path names then you need to ensure the system clock on the sending machine is in synch with that on the domain controllers. This is because kerberos authentication will fail if you let enough gap exist between the clocks (45 seconds, in fact). Without that you cannot query active directory for the properties of the public queue.
One symptom of this is
You may also receive "0xc00e0044 MQ_ERROR_INVALID_OWNER (The object owner is invalid (for example, MQCreateQueue failed because the
QM object is invalid)."
In fact there's probably a whole bunch of error codes you could get back, depending on what you are trying to query active directory for. All will be misleading in this case so make sure you configure every machine to use one or more authoritative time servers. For example:
NET TIME /SETSNTP: ntp2d.mcc.ac.uk
If you want to set up your own authoritative time server then these KB articles are a good place to start: