I had the same error message and the solution was simple.
There were a lot of messages sitting on various queues, and the storage limits had been reached. I went to:
Server Manager -> Features
Right clicked on Message Queuing
Selected properties
In the General tab un-ticked the storage limits
I was informed that services using MSMQ would be re-started, and then the error went away.