Обработка команды-не-найдена без PackageKit

Запустив chmod 777, вы удалили бит setuid в pppd. Для его восстановления нужно запустить

chmod 4755 /usr/sbin/pppd

Обратите внимание, что, запустив рекурсивную chmod 777таким образом, вы, вероятно, нарушили другие разрешения и, безусловно, сделали свою систему довольно небезопасной.