Ооо, я заебался
Нахрен нужен ноутбук, если в инет с него можно выйти только из дома, кафешки и ещё нескольких мест с открытыми WiFi-сетками?
Но, как это ни печально, в дебиане с жпрсом полный пиздец. Network Manager, в отличие от убунтовского, о нём и понятия не имеет, а gnome-ppp не работает без напильника. Для начала, чтобы он работал не только под рутом, делаем так:
chmod +s /usr/sbin/pppd
chmod +x /usr/sbin/pppd (на счёт необходимости этого не уверен, но уже сделал и переделывать не буду)

Теперь запускаем утилитку, вбиваем логин/пассворд и номер дозвона. Лезем в настройки и снимаем к такой-то матери все галки (для мобильного инета эти параметры не нужны), меняем ужоснахную строку в init2: на ATZ, вписываем Init3: AT+CGDCONT = 1,"IP","internet.mts.ru" (или что там у нас), жмём на дозвон и радуемся интернету... Если у нас не мегафон, конечно

У мегафона нет логина и пароля - звонилке это не по нраву. Пробовал и так и раком^Wсяк - ей даже параметр noauth похуй (как выяснилось, умная прога при запуске откатывает все мои изменения)
Вот что она по этому поводу сгенерировала: wvdial.conf

Ок, мы трудностей не боимся! идём в /etc и правим wvdial.conf там. Запускаем из консоли - видим всё тот же мпх... Добавляем параметр noauth, Ask Password = off, запускаем, с чувством произносим: "Блядь!" и идём биться о стену

Update:
Разрулено. Вводить можно любые логин и пароль, но буквами - без цифр.