Mail: Password Problem

I get this message when I open Mail.app:

Mail cannot verify the identity of mail.[domain_name].co.uk
The certificate for this server was signed by an unknown certifying authority. You might be connecting to a server that is pretending to be mail.[domain_name].co.uk which could put your confidential information at risk. Would you like to connect to the server anyway?

Click to expand...

I can get on if I click 'Connect' but I have to do this every time I re-launch.

If I click 'Show Certificate', I can check a field that says: "Always trust ***.pacwebhostingltd.com when connecting to mail.[domain_name].co.uk"

Apparently the certificate is already marked as trusted for all users so I don't understand why I need to do this every time I re-launch. Any ideas?