Base on this consideration:

• If the DocuSign Service Instance is registered using the K2 Integrator Key option, DocuSign does not require certification. If you use your own Integrator Key provided by DocuSign when enabling the feature, certification is required. Certification allows for the Sandbox Integrator Key to be used against DocuSign’s Production Service Address. See the DocuSign article which explains this in more detail: https://www.docusign.com/developer-center/go-live/certification

https://help.k2.com/onlinehelp/k2blackpearl/userguide/4.7/default.htm#K2_Management_Site/Features/DocuSign.htm

I assume you are using your own Integrator Key and as such certification is required?

I assume this post brought you to the certificates:

https://support.docusign.com/en/articles/Connect-Error-The-remote-certificate-is-invalid-according-to-the-validation-procedure

In which case, the DocuSign Connect x.509 public certificate was downloaded and installed from:

https://trust.docusign.com/en-us/trust-certifications/docusign-public-certificates/

I supposed this was intalled on the Local Machine against the Trusted Root Certificate Authorities?

Additionally, is K2 installed in a farm setup with more than one K2 server node?  If 50%/50% intermittentness, perhaps the cert was only added to one of the K2 server.

Thanks for the response, and this was attempted at first with no luck.

Solution: The SOAP and REST urls in the DocuSign service instance were pointed at www addresses.  I was asked to swap these to NA2 and this worked after restarting services and resetting IIS.