Кучу времени уже потратил на попытку разобраться в аналогичной проблеме. Столкнулся на девятом Дебиане, либы обновлены до последних версий.
Чтобы радикально исключить версию со старыми либами (мало ли, этож Дебиан, версии либ отстают) проверил на свежеустановленном специально для этой цели Убунту-сервере, 17й версии.
Попытки найти ответ на вопрос в гугле, либо соответствующих группах телеграмма, ничего не дали.
В итоге перешел на этот бот
https://github.com/python-telegram-bot/python-tele...
Вот о настройке его работы через прокси
https://github.com/python-telegram-bot/python-tele...
Причём если прокси с авторизацией, у меня работал только первый способ.
Кстати, этот бот по числу звёзд популярнее telebot, хотя отличия между ними мне не совсем понятны. Telebot использует декораторы, код получается лаконичнее и красивее.