Здравствуйте!
У меня точно такая-же ситуация в Альт Линукс 4.0 Лайт.
В интернете, в описаниях настроек соединения с Мегафон в Виндовс, упоминается, что должны быть обязательно включены расширения LCP. Может быть, в эту сторону смотреть? (Т.к. с сим-картой Билайн, припоминается, все работало).
Я сам пытался править файл "options", но ничего не добился. Т.е. через несколько секунд (после перебора DNS - разобрался с помощью участников этого форума) сервер перестает отвечать.