COM+ Queued component : Error 80080005 Server execution failed. Error Code = 0xc00e0003

On a windows server 2003, we are not able to start a Queued COM+ application. It fails with the error: 80080005 Server execution failed.
In the event logs we see the following entries :

Event Type: Error
Event Source: COM+
Event Category: (115)
Event ID: 4811
Date: 12/24/2010
Time: 4:27:39 PM
User: N/A
Computer:
Description:
An unexpected error was returned by Message Queuing API indicated. Unable to retrieve the associated error message text. Message Queuing API return values are defined in Platform SDK file MQ.H.MQPathNameToFormatName

Server Application ID: {45445320-4154-4C41-4E54-455320382E30}
Server Application Instance ID:
{8AAA34A0-076F-4D41-9751-F7D973F5C81A}
Server Application Name: ACM80
Error Code = 0xc00e0003 :
COM+ Services Internals Information:
File: d:\nt\com\complus\src\comsvcs\qc\msmqrt\msmqrt.cpp, Line: 749
Comsvcs.dll file version: ENU 2001.12.4720.4045 shp

Event Type: Error
Event Source: COM+
Event Category: (104)
Event ID: 4811
Date: 12/24/2010
Time: 2:45:16 PM
User: N/A
Computer:
Description:
An unexpected error was returned by Message Queuing API indicated. Unable to retrieve the associated error message text. Message Queuing API return values are defined in Platform SDK file MQ.H.MQOpenQueue

Server Application ID: {45445320-4154-4C41-4E54-455320382E30}
Server Application Instance ID:
{21B51AB1-552F-4FDE-AEC4-9CD7ED000EF0}
Server Application Name: ACM80
The serious nature of this error has caused the process to terminate.
Error Code = 0xc00e0003 :
COM+ Services Internals Information:
File: d:\nt\com\complus\src\comsvcs\qc\listener\listener2.cpp, Line: 532
Comsvcs.dll file version: ENU 2001.12.4720.4045 shp

For more information, see Help and Support Center at https://go.microsoft.com/fwlink/events.asp.

 

Error code 0xc00e0003 indicates MQ_ERROR_QUEUE_NOT_FOUND.

We opened Computer management and checked the private queues. The private queues for the COM+ application were missing. Ideally, when we configure queuing on the COM+ application it creates the private queues for the COM+ application.
We unchecked the "Queued - This application can be reached by MSMQ queues" option on the COM+ application to disable queueing. Selected the option again to re-enable queueing. Checked the private queues and now we can see the private queues created for the COM+ application.
Started the COM+ application and boom.. it's started.