Something appear to be broken between the Android SSL library used by K-9 Mail (and the native Android "E-mail" client), and the 1.0.0 openssl in 12.04 as used by sendmail. I am seeing this error with K-9 Mail clients trying to talk to sendmail:
http://code.google.com/p/k9mail/issues/detail?id=3022
If I downgrade the sendmail-bin package to the version from Natty (which uses openssl 0.9.8), everything is fine again. Oddly, the logs in K-9 Mail show successful post-SSL-handshake communication. It is extremely unclear what is going on here.
Since nothing changed in the sendmail package between natty and precise, I'm opening this against openssl. The problem could probably be anywhere in openssl, sendmail, K-9 Mail, or the Android SSL libraries, but there is at least a visible regression seen when changing from 0.9.8 to 1.0.0 on Ubuntu. :(
FWIW, the solution for LP: #1018998 did not fix this problem.