To novicoff:Увы, моих знаний пока что не хватает, чтобы однозначно выявить проблему.
Единственное, в чём я уверен - это в том, что сразу после загрузки соединение всё-таки есть, только оно по каким-то причинам не работает. Если после загрузки запустишь какую-то утилиту сетевого мониторинга, например pppstatus или Network Monitor - несомненно покажет, что сеть есть, и даже передаются какие-то пакеты. Поэтому этап 2 наверное можно пропустить - попробуй сразу после загрузки сделать sudo poff dsl-provider (ну или просто sudo poff), а потом снова pon.
В остальном все параметры, на мой взгляд, нормальные, за исключением route. В первом варианте он такой же, как был у меня, когда у меня инет не работал. Но у меня это было из-за отсутствия dns в resolv.conf. Когда я их туда прописывал - всё тут же начинало работать. А почему у тебя так - непонятно.
plog ничего интересного не выдаёт - у меня после загрузки он пустой, независимо от того, работает инет или нет. Приведенные строки
Apr 27 19:37:53 noname pppd[3434]: Connection terminated.
Apr 27 19:37:53 noname pppd[3434]: Modem hangup
означают только, что соединение было отключено, и появляются они после команды poff.
В файле интерфейсов, который я приводил для примера, у меня тоже сначала auto eth0 был последним. И я его тоже переместил вперёд, в надежде починить свой инет

И мне точно так же это не помогло

Хорошо хоть помогло другое.
IP в выводе ifconfig меняется потому, что дом.ру выдаёт IP в основном динамически - это так и должно быть. Если всё остальное не меняется - я бы предположил, что дело не в настройке параметров интерфейсов...
Проблема очень похожа на ту, что была у меня. Но раз dns есть - значит, дело не в них. Но всё-таки проверь ещё раз, одинаковые ли они сразу после перезагрузки и когда инет работает.
Кстати, как ведёт себя браузер сразу после перезагрузки? Какое сообщение выдаёт? Что будет, если пингануть какой-нибудь быстрый и надёжный сайт, например ya.ru? Если браузер мгновенно, без раздумий говорит что-то вроде "сайт ya.ru не может быть найден", а ping, опять же мгновенно - "unknown host ya.ru" - значит, дело всё-таки в dns. Если браузер долго тупит и в конце выдаёт другое сообщение об ошибке, а пинг всё-таки пытается отправлять куда-то пакеты и потом говорит, что они потерялись - значит, dns ни при чём.
Если бы проблема была у меня - начал бы пробовать всякие шаманские манипуляции, прихлопы и притопы

1. Удалил бы из dsl-provider опцию usepeerdns - отвечает за автоматическое получение dns от провайдера. А сами dns попробовал бы прописать в resolv.conf вручную, такие, какие они у тебя после того, как всё нормально заработает. После этого попробовал бы перезагрузиться - заработает или нет.
2. Отключил бы опцию replacedefaultroute в dsl-provider - отвечает за замену маршрута по умолчанию. Перезагрузился.
3. Отключил бы defaultroute - а роутинг прописал бы вручную. Опять перезагрузился бы.
Если ничего не помогло - забэкапил бы файл interfaces, убрал бы оттуда всё кроме lo, и попробовал бы снова поставить NetworkManager и всё, от начала и до конца, настроить с его помощью. Говорят, в 9.04 он стал лучше, и можно им всё настроить - только до этого надо удалить всё, что прописано в конфигах без его участия. Вдруг поможет.
Если и так не получилось - позвонил бы в техподдержку провайдера, у дома.ру они быстро отвечают, и по телефону, и по аське. Может, посоветуют что-то дельное.
Если и провайдер не помог - окропил бы комп святой водой

На этом у меня пока идеи закончились бы - убрал бы снова все соединения NetworkManager, настроил бы опять через pppoeconf, но только без автозагрузки. Сделал бы скриптик, и поднимал бы соединение после загрузки вручную. И ждал бы - может, какая мысль новая появится, или на форуме кто-то что-то дельное напишет, или обновление от Canonical придёт.