I am trying out the new REST API Get Deleted Objects Resource in the Winter '14 release.  When I try to make a call to the API using the URI like the one in the Release Notes:

/services/data/v29.0/sobjects/Contact/deleted/

?start=2013-05-05T00:00:00+00:00&end=2013-05-10T00:00:00+00:00

I get the error:

"Error parsing the 'start' date string. This operation requires properly formatted 'start' and 'end' date/time parameters to be specified. Please consult the documentation for the format of these date/time fields."

I am calling this from a C# program which works fine for other REST API calls, I just can't seem to get this one to work.

Which editions of Salesforce is the REST API available in? Is it like the Web Service API where it is only available in Enterprise and Unlimited?