WebInvoke Method=POST Generic Server Error

[=?Utf-8?B?Q2FtaWxvIE9yb3pjbw==?=]

When I call an operation from my contract that has been decorated with
webinvoke and a payload is sent, the server always returns a generic error
(400). If I make the same POST request with no payload, the call goes through
with a value of null for the parameter.

Here's some reference code:

[OperationContract]
[WebInvoke()]
string Test1(string testparam);

public string Test1(string testparam)
{
return string.Format("Callin Test1...{0}", testparam);
}

On Fiddler this is the request I make:

POST /RESTCatalogService.svc/Test1 HTTP/1.1
User-Agent: Fiddler
content-length: 28
content-type: application/xml
host: localhost:44929

<testparam>abcde</testparam>

This request fails with a 400 error: "The server encountered an error
processing the request", if I don't send the testparam payload, the method
gets executed with no problems.

Any insights on this would be really appreciated.