To be clear, this project isn't endorsed in any way by Open Whisper Systems. We forked their codebase pre-v2.7.0 and are integrating upstream commits, but that's it.
The idea isn't to compete with TextSecure, it's to provide the encrypted SMS functionality TextSecure used to (with all it's compromises and drawbacks) for people that push-based messaging isn't an option for.
How did you guys attack this problem?
We're using the same system we inherited from TextSecure for encrypted SMS: Trust keys implicitly on first use, while encouraging users to verify them out of band.
The verification is handled by providing a screen that has your identity and what you think the recipient's identity is. If the recipient's identity matches what your app says and vice-versa, then you know you're talking to the right person.
Ideally, the verification would be done in-person or via another secure means of communication. Currently you can verify identities by just reading them out, or via QR code.