Check that the service has permissions to access its MSMQ queues.
Is the MSMQ Primary Enterprise Controller or Backup Enterprise Controller running?