I have an Apex REST service that up until today was fully functional. It's in two sandboxes, one on Spring '13, one on Summer '13 preview, and both are throwing the same error. Now when I send in a valid request, such as:

<request>
<FirstName>Matthew</FirstName>
</request>

I'm nearly immediately returned the following:

HTTP/1.1 400 Bad Request
Date: Mon, 20 May 2013 21:20:21 GMT
Content-Type: application/xml;charset=UTF-8
Transfer-Encoding: chunked


<?xml version="1.0" encoding="UTF-8"?>
<Errors>
    <Error>
        <errorCode>XML_PARSER_ERROR</errorCode>
        <message>Unexpected parameter encountered during deserialization: FirstName</message>
    </Error>
</Errors>

I've tried the same with JSON, and get a similar JSON_PARSER_ERROR with the same message, "Unexpected parameter encountered during deserialization"

Also took a look at a debug log and it only has a handful of lines.

27.0 APEX_CODE,DEBUG;APEX_PROFILING,INFO;CALLOUT,INFO;DB,INFO;SYSTEM,DEBUG;VALIDATION,INFO;VISUALFORCE,INFO;WORKFLOW,INFO
17:20:21.031 (31030000)|EXECUTION_STARTED
17:20:21.031 (31075000)|CODE_UNIT_STARTED|[EXTERNAL]|01pZ00000005X08|REST_AutoRenewalService_V1.doPost
17:20:21.035 (35960000)|CODE_UNIT_FINISHED|REST_AutoRenewalService_V1.doPost
17:20:21.035 (35978000)|EXECUTION_FINISHED

Has anyone seen this error before or have any idea how to fix it?