There is a new WhatsApp-killer application called Telegram. They said that it's open source and that it has a more secure encryption.

But they store all the messages in their servers and WhatsApp doesn't store any messages in any server, only a local copy in the phones.

Is Telegram more secure than WhatsApp?

TL;DR: No, Telegram is not secure.
I'd like to ignore the comparison to WhatsApp because WhatsApp does not advertise itself as a "secure" messaging option. I'd like to instead focus on whether Telegram is secure.
Telegram's security is built around their home spun MTProto protocol. We all know that the first rule of Cryptography is Don't Roll Your Own Crypto. Especially if you aren't trained cryptographers. Which the Telegram people most certainly aren't.

The team behind Telegram, led by Nikolai Durov, consists of six ACM champions, half of them Ph.Ds in math. It took them about two years to roll out the current version of MTProto. Names and degrees may indeed not mean as much in some fields as they do in others, but this protocol is the result of thougtful and prolonged work of professionals.

Source: https://news.ycombinator.com/item?id=6916860
Math Ph.Ds are not cryptographers. The protocol they invented is flawed. Here is a nice blog post explaining why. In addition to that, Telegram has issued a rather ridiculous challenge offering a reward to anyone who can break the protocol. Except that the terms they set makes even the most ridiculously weak protocol difficult to break. Moxie Marlinspike has a nice blog post explaining why the challenge is ridiculous.
So, no. Telegram is by no means secure. For commonly accepted definitions of secure, not the one Telegram made up.
If you want a real secure means of communication on your phone, look to more reputable projects such as Signal or WhatsApp (which, since this answer was first written, now uses the Signal Protocol for end-to-end message encryption).
UPDATE

09 January 2015: A new 2^64 attack On Telegram has been
announced.
12 December 2015: A new paper demonstrating that
MTProto is not IND-CCA secure.
22 December 2017: Replaced outdated recommendation for
CryptoCat with a more up-to-date recommendation for
Signal and WhatsApp.

