The trouble has been resolved thanks to Kevin and Brian.
What appeared to have been a faulty patch, multiple certificates were loaded to all servers including the email servers. The number of Certs. caused the servers to fail to communicate with each other. We are not sure why it happened now, since the patch was released in Dec of 2012.