Dave,
As RMG pointed out, please make sure that you have the complete certificate chain within your WM setup:
1- Try adding the CA certificate first in the TN console
2- CA that issued this certificate must be trusted, i.e., in the trusted CA directory (this usually requires a re-start of wm server).
I took a while, but the resolution to this issue was the certificate serial number. Aparently, webMethods does some pretty extensive AS2 certificate validation through the entrust libraries that are built into Trading Networks. With the help of webMethods support, we found out that the trading partner’s certificate serial number was 00 00 00 01. According to the Drummond group’s AS2 certification, the leading-order values cannot be 00. The trading partner changed their certificate serial number to read 01 00 00 01 and it loaded into TN just fine.