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

I'm writing messages to a Message Queue in C# as follows:

queue.Send(new Message("message"));

I'm trying to read the messages as follows:

Messages messages = queue.GetAllMessages();
foreach(Message m in messages)
{
  String message = m.Body;
  //do something with string
}

However I'm getting an error message which says: "Cannot find a formatter capable of reading this message."

What am I doing wrong?