Странное объяснение, т.к., например, в EnvelopedSignature цепочка не строится и не проверяется. Аналогично, наверно, и в вашем коде, где вы, полагаю, использовали низкоуровневые вызовы с участием сертификата только для согласования ключей и расшифрования. Если расшифрование произошло на вашей стороне без каких-либо видимых изменений в коде, то, вероятно, проблема была на стороне отправителя.