Some questions whose answers may be relevant:
- Are you accessing your server by name or IP address?
- If you login to WEBmail and look at your server's certificate, does it match the name or ip you are using to access your server?
- Did you "install" or "trust" your server's old certificate on your client system?
- Is your mail client still talking to the old IP address (now someone else's server) for SMTP?
- Is your mail client using smtps with authentication, or had you configured your server to allow email relay without authentication?