Korean developed and Japan based Line is the number one, feature laden, client in SE Asia these days, particularly in Thailand. Hardly anyone uses Whatsapp over here these days, especially since Facebook took over. Line is available for most platforms (Windows, OS X, iOS, Android), apart from Symbian and Linux, so no good for a Nokia N8 (which is what I currently have):
Easy to use interface, and free to use and free of ads. Plenty of downloadable emoticons, emojis, games etc. It's becoming a bit of a platform in it's own right.
Fits all of your requirements, except end-to-end encryption. I used it a lot when I had an iDevice, a good fun comms app. Totally recommend.
China's Wechat is another big messaging app over here too. And it is available for the N8.
End to end encryption
However, Line and Wechat are not end-to-end encrypted messengers. For that, you are best off with the Swiss Threema (very big in Germany, again especially since Facebook ate Whatsapp) or one of the previously mentioned Telegram, RedPhone, TextSecure and Surespot. Threema I like a lot, as it has many of Whatsapp's features. No video calls though, although you can send video.
Obviously, your end choice of app will also depend on which platform your colleagues and friends are using, or are willing to switch to. Probably best to go for a bit of a mix. But my votes go to Telegram, Threema and Line.