Around 2:30pm on Friday, the chain cert was properly installed on the server and after that most of clients began working again. At least one user is still experiencing issues with Windows Mobile and Xpressmail.
UPDATE
[2009-11-05 09:27:08 | Eric Fraser]
The one remaining open issue with the Certificate upgrade was with an Xpress Mail client. The vendor has confirmed that they do not yet support 2048-bit certificates.
Resolved as of 2009-11-05 09:22:00