Message Queue Error: cannot find a formatter capable of reading message

you could try reading the bodystream of the message instead of the body, like this:

StreamReader sr = new StreamReader(m.BodyStream);    
string messageBody = "";    
while (sr.Peek() >= 0) 
{
    messageBody += sr.ReadLine();
}

Or you can use

 message.Formatter =
     new System.Messaging.XmlMessageFormatter(new Type[1] { typeof(string) });

Message recoverableMessage = new Message();
recoverableMessage.Body = "Sample Recoverable Message";

recoverableMessage.Formatter = new XmlMessageFormatter(new String[] {"System.String,mscorlib" });

MessageQueue myQueue = new MessageQueue(@".\private$\teste");

Queue must be set Formatter too.

myQueue.Formatter = new XmlMessageFormatter(new String[] { "System.String,mscorlib" });

I solved the problem by adding a formatter to each message. Adding a formatter to the queue didn't work.

Messages messages = queue.GetAllMessages();
foreach(Message m in messages)
{
  m.Formatter = new XmlMessageFormatter(new String[] { "System.String,mscorlib" });
  String message = m.Body;

  //do something with string
}