Ну значит проблемы с MTU.

Посмотрите, какое значение у вас выставлено?
sudo bash
cat /etc/network/interfaces

И попробуйте поизменять значения для MTU.
Попробуйте поставить MTU 1400 или еще меньше.
.

Ну и скажите нам, что получилось...

Почему-то значений MTU нет:

unterton@unterton:~$ sudo bash
root@:unterton:~# cat /etc/network/interfaces
auto lo
iface lo inet loopback

В сети нашел, что MTU можно изменять вот этой командой sudo ifconfig ppp0 mtu 1400, но пока не осмелился (вдруг что нибудь сломаю)

Да, можно и так. Но это надо делать каждый раз тогда.

Не бойтесь, не сломаете. :)

Ура! Интернет заработал.
Да, команду приходится вводить каждый раз при включении компьютера (но это не страшно).
Теперь буду искать решение, как это все автоматизировать.
Благодарю за помощь!