I also struggled with setting up Open Keychain with K9 Mail, and I was able to solve it.
Even though the recipient's key was in Open Keychain, and even though Open Keychain was selected from Settings>Account Settings>Cryptography, when I tried to send to send an encrypted message, it would show the message that said "private mode is enabled but some recipients don't have keys."
What I did to solve it was to open Open Keychain and select the recipient's certificate, click the three dots in the upper right corner, and then selected "Confirm with fingerprints>Finger Prints Match > Confirm Key
That turned the contact a green color in Open Keychain.
Finally, I went back into K9 Mail, and was able to send encrypted emails.
I don't know if my experience was unique, but thought I would share it since it took me hours to solve this problem.