Проблема в том, что алгоритм по умолчанию, используемый CmsSign, должен быть тем же алгоритмом, который использовался для создания ключа сертификата, в моем случае, SHA1.
Вот как было загружено для сертификата S / MIME:
X509Certificate2 cert = new X509Certificate2(@"ca.p12", "xpto", X509KeyStorageFlags.Exportable);
var signer = new CmsSigner(cert);
signer.DigestAlgorithm = DigestAlgorithm.Sha1;
MultipartSigned.Create( signer, mimeMessage.Body);