Sounds like the client is not accepting the certificate.
did you change the certificate of the server recently ?
I think you need to accept the new certificate on the client software.
In K-9 it is in Settings > accounts > Fetching mail > Incoming Server > Next of Advanced
and accept the new certificate.
Yes, indeed accepting the new certificate solved the problem.
But should K-9 not show a warning when the SSL-certificate changes ?
instead of doing nothing ? It is confusing.