ADO.NET Data Services contain information in the URI that are used to identify which resource is being addressed. Part of this information is the value for the primary key in the database. For example, if one of the key values is abc, the URI might look like http://server/service.svc/EntitySet('abc')
Unfortunately, this can cause problems for certain values when validation is too aggressive. Typically there are ways to turn these off, and here's one example.
KB 826437 at http://support.microsoft.com/kb/826437/en-us describes how to modify the registry to allow certain characters (including & and :) to pass through ASP.NET (the flag is set at the machine level). If you're running into this problem, you'll see it manifests as a 400 - Bad Request reply and the returned body shows <html><body>Bad Request</body></html>.
This is a pretty telling sign, as ADO.NET Data Services doesn't format its error messages as HTML (not at the moment, anyway). You can therefore conclude that the request is getting rejected at a different layer - in this case, ASP.NET.
This posting is provided "AS IS" with no warranties, and confers no rights.