Dovecot (IMAP) is working fine here with K-9.
Since you're seeing different results in different clients, the most
obvious reason would be a different behavior from the two different ways
to connect to IMAP (or POP3) with TLS:
* connect to port 993, start TLS negotiation
* connect to port 143, run STARTTLS command, start TLS negotiation
(with POP3 it'd be 995 and 110).
You can debug both with OpenSSL's s_client:
openssl s_client -starttls imap -connect MAIL.YOURDOMAIN.COM:imap
openssl s_client -connect MAIL.YOURDOMAIN.COM:imaps
(or of course change all the imap to pop3 to do POP3).
If you're seeing this on sending mail, that's SMTP — and there are
/three/ SMTP ports you might be using: 25, 465, and 587. 25 and 587 need
STARTTLS. s_client can deal with those, too.
Once you've figured out what's happening, then you can determine if it's
something weird on your server or your VPS providers' network.