MSMQ access denied when reseting permissions

I am trying to initialize a private MSMQ and set permissions to Everyone using code:

string queuePath = "test_queue";

if (!MessageQueue.Exists(queuePath))
{
     try
     {
            MessageQueue.Create(queuePath, true);
     }
     catch (MessageQueueException exc) when (exc.MessageQueueErrorCode == MessageQueueErrorCode.QueueExists) 
     { 
     }
}

_messageQueue = new MessageQueue(queuePath, true, true, QueueAccessMode.Receive)
{
     Formatter = new XmlMessageFormatter(new Type[] { typeof(String) })
};


_messageQueue.ResetPermissions(); //Here is where I get exception

AccessControlList permissions = new AccessControlList()
{
      new AccessControlEntry(new Trustee("Everyone"),
                               GenericAccessRights.All,
                               StandardAccessRights.All,
                               AccessControlEntryType.Allow)
};

_messageQueue.SetPermissions(permissions);

The exception I get in _messageQueue.ResetPermissions() line is:

Starting monitoring failed, an unexpected exception occured: System.Messaging.MessageQueueException (0x80004005): Access to Message Queuing system is denied.

So it's saying I do not have access to that private queue. I can't reproduce this issue on my local dev machine, but it is reproducible on external machines. Also, it is reproducible only first time when queue is created, when I manually delete test_queue from Computer Management after this issue occurs and run the program again I do not get System.Messaging.MessageQueueException exception ever again.

Any suggestion what could be the issue?