[Windows Phone 8 Apps and Games] GoodDayToDie:
I have no personal knowledge of one, sadly. Take anything I say here with a huge grain of salt (including the fact that Sicher looks like a scam; I haven't actually verified that it *uses* all those ad networks + Facebook that it integrates, just that it has them) as I'm not spending the time & effort for a full security review of these apps at this time.

Threema actually looks quite good.

Pros:

They don't try to implement the crypto themselves (they use NaCl, which is both written by people who know what they're doing, and well-reviewed).

The design of their end-to-end solution makes sense (it connects through the server since phone networks won't allow incoming/direct connections, but the messages are encrypted to only the recipient and doesn't require that the recipient be online to receive the message).

They are relatively open about how things work (although those *could* be lies; I haven't pulled the app apart).

It is possible for the user to verify the key of another user.

Cons:

They don't have Perfect Forward Secrecy on messages. PFS would require that the intended recipient be online at the start of any given conversation (to negotiate the ephemeral keys) so this isn't terribly surprising, but it is disappointing. An attacker (including a government agency) who gets access to your private key could decrypt historical traffic to you if they'd recorded it.

The app is proprietary; there's nothing stopping them from pushing a malicious update.

The server supplies the public keys of users; until such time as the user validates the other party's key (which is difficult to do except in person) the server could have sent a public key that the server has the private key for (instead of the user's own public key) and then MitM the user's traffic. This would break down when verified though, unless the app lied about the result of the verification process (you don't actually see the key itself).

To address your concern about MitM, the app says they use certificate pinning (a standard and very smart security measure, assuming they did it right) for app-to-server communication, so nobody (including third-party security engineers) can MitM the app traffic. They also claim to use PFS. However, if the server itself is untrusted (i.e. some government thugs show up to demand access, although bear in mind that apparently the servers are all in Switzerland) then the server could give you the wrong public key for a user you try and add, allowing the server to MitM you. Also, the company could push an update that is malicious.

The only protection against the server-sends-wrong-key threat is to either require that the user manually import all keys (think PGP minus keyservers and assuming trustworthy key exchanges) or exactly verify the key (i.e. personally ensure that it matches the other user's key by actually checking the bytes or at least the hash). The only protection against the malicious update is to make the source code available and have a method by which users can either compile it themselves (though see "Reflections on Trusting Trust") and/or have a way to verify the application binaries.

I'll look at Telegram later. For the moment, though, I would loosely recommend Threema once it's available. There's also Skype, of course, but while it was decompiled once long ago (and found to use secure encryption, although some non-crypto vulns were found) that was many versions ago (and, in particular, was before Microsoft bought them).