I had this error and wanted to leave one solution for anyone else who may get this in future. I was attaching a PDF from an SSRS report to an email and giving it a custom filename in a workflow.

The constructor to deserialize an object of type 'Microsoft.Exchange.WebServices.Data.CreateAttachmentException' was not found.

After troubleshooting I found the stored proc which returned the filename for the document to be attached, returned nothing which prevented the attachment and caused the failure.