Time on the server is correct Sam. Which SSL libraries does Discourse need the mail server to have?
The thing that makes this odd is that (Apple) Mail is usually very quick to warn of issues, yet the same emails work fine on my Mac.
The only other thing I can think of is DNS propagation because this is a new sever and the email host was slightly different on the old server (but the email is being hosted on the same server as the forum so not convinced this would be the issue).