На 16.04 скачанный с офсайта бинарник работает?
Да, работает. Для пробы сейчас в Xubuntu 16.04 x64, которая в виртуалке, скачал, в терминале набрал sudo mc, распаковал в /opt и запустил /opt/Telegram/Telegram - появилось окно входа и предложение отсканировать QR-код и на этом я опыты закончил.
Кстати, в меню автоматически появился пункт Telegram в разделе Интернет, что позволяет при необходимости вытащить десктоп-файл на раб.стол