When I try to test the queue via the Message Bus. I've checked and permissions are set to full control for everyone. I use 'msmqmng.exe send' from a different machine to put a message onto the queue, it works and is absolutely the message I sent. So what other moving parts might I be missing???
I spent couple of days banging my head for this error, and the root cause was that the storage quota for MSMQ was exceeded! which doesn't seem related to the error message, which makes it a difficult cause to detect...
When sending a message to MSMQ, the sender server will use an outgoing queue located on the sender side, and this outgoing queue is using the storage on that sender server. The MSMQ component has a maximum quota, defined in the MSMQ properties, and when this quota is exceeded, the above error message starts popping (that's why when you sent from another machine, it worked correctly, since the issue is with the sender not the receiver).
Resolution: To change this quota, right click on Message Queuing (from Computer management if using Windows server 2003 for example) then properties... (I cannot post images since i am a new user), but in the properties window, you will find in the first tab an editable storage limit field.
To check the currently used storage on the server, open the path of the storage, and check its size: (open the storage tab in the same properties window, and get the path of the storage folder) If the size of the quota is similar to the size of the storage folder, then this is the root cause of your issue.
If you dont have permission to increase this quota limit, you should have your user added to the "Security" tab in the message queuing properties window.
Hope this helps... Please vote up if you agree in order for me to have some points and post images in my next answer... :-)