I’ve successfully added my mail account to K9 and can receive mail without problems, but I can not send mails.
Sending mails always fails with “Cannot connect to server. (Unexpected character:* (42))”
I use SSL/TLS with port 993.
In my case I fixed the problem by changing the port to 587 and using STARTTLS instead of SSL/TLS for the outgoing mail server (“Account settings” → “Sending mail” → “Outgoing server”).
With IMAP, the port for incoming mail is 993 (or 143 if not using ssl/tls). Outgoing is 465 and/or 587 (depending on your provider’s setup). So, based on the above, the fix for your outgoing mail problem was not so much that you changed from ssl/tls but rather from 993 to 587.