400 bad request sending xml payload to WCF REST se

I know there are a few posts asking about the 400 error, and I believe I've read all of them, but I think the problem I'm facing is different.

This is my WCF service contract

[WebInvoke(UriTemplate = "/cust_key/{key}/prod_id/{id}", 
           Method = "POST",
           BodyStyle = WebMessageBodyStyle.Bare, 
           RequestFormat = WebMessageFormat.Xml, 
           ResponseFormat = WebMessageFormat.Xml)]
Stream GetData(string key, string id, string data);

And this is the code that I use to send the request to my rest svc

request.RequestUri = 
     new Uri("http://localhost:3138/v1/cust_key/company1/prod_id/testProductID");
request.ContentType = "application/xml";
request.HttpMethod = "POST";

string xml = 
         @"<Product><name>dell 400</name><price>400 dollars</price></Product>";

byte[] message = Encoding.ASCII.GetBytes(xml);
string data = Convert.ToBase64String(message);
response = request.MakeWebRequest(null, data);

This gave me 400 bad request error. I've tried to change the xml string to the following two and they also produce 400 error

<string xmlns="http://schemas.microsoft.com/2003/10/Serialization/">
       <![CDATA[<Product><name>dell 400</name><price>400 dollars</price></Product>]]>
</string>

<![CDATA[<Product><name>dell 400</name><price>400 dollars</price></Product>]]>

If the payload xml is empty string, then everything is fine and 200 is returned. Can anyone give me a hand?

Edit: my web.config section. it comes out of box from the WCF REST Service Template 40(CS)

<system.serviceModel>
 <serviceHostingEnvironment aspNetCompatibilityEnabled="true"/>
  <standardEndpoints>
  <webHttpEndpoint>
    <!-- 
        Configure the WCF REST service base address via the global.asax.cs file and the default endpoint 
        via the attributes on the <standardEndpoint> element below
    -->
    <standardEndpoint name="" helpEnabled="true" automaticFormatSelectionEnabled="true"/>
  </webHttpEndpoint>
</standardEndpoints>

Your second example using the <string> element should work. If you know the schema of the XML that you are recieving, you can do the following:

[WebInvoke(UriTemplate = "/cust_key/{key}/prod_id/{id}", 
       Method = "POST",
       BodyStyle = WebMessageBodyStyle.Bare, 
       RequestFormat = WebMessageFormat.Xml, 
       ResponseFormat = WebMessageFormat.Xml)]  
//Almost exacely the same except String is now Product in the method Parameters
Stream GetData(string key, string id, Product data);

[DataContract(Namespace = "")]
public class Prodect
{
    [DataMember]
    public string name { get; set; }
    [DataMember]
    public string price { get; set; }
}

Then use the client code from your post and it should work fine. On the other hand, if you want your web service to dynamically accept different XML that are not well defined data contracts you can use XElement as follows:

[WebInvoke(UriTemplate = "/cust_key/{key}/prod_id/{id}", 
       Method = "POST",
       BodyStyle = WebMessageBodyStyle.Bare, 
       RequestFormat = WebMessageFormat.Xml, 
       ResponseFormat = WebMessageFormat.Xml)]  
//Almost exacely the same except String is now XElement
Stream GetData(string key, string id, XElement data);