In working with the SharePoint web services, I've noticed consistent errors with a few of the services which tend to return the following string:
String was not recognized as a valid DateTime
I hadn't been able to figure out what exactly the error was until today.
It's actually not related to a date/time string at all, but rather, the root of the error is in the service implementation itself. The actual underlying error is an error indicating that a field value is no longer valid. For example, if the item had a field referring to a lookup list, changes in the target list may invalidate a value on a given item. Instead of returning a useful error, the web service returns the error above.
You may find this error when using the lists.asmx service or the dspsts.asmx service.
I "fixed" this by removing the offending field from the content type and also from the list and voila, no more errors.
It's hard to track down because the SharePoint itself will render the properties without any error indication in the view and edit properties view, but it will fail the entire request if one field is invalid and return a useless SOAP error.