avtoremove работает по меткам что ставилось вручную. Магии никакой нет, если верхушка графа зависимостей удаляется, то autoremove может удалить пакеты, которые ставились не вручную, а по зависимостям автоматически. Ну т.е. я не верю что удаление telegram может привести к таким последствиям в autoremove. Чудес не бывает, должно быть объяснение, математическое.