Cynik, ну так сами же предложили решение. Перезагрузиться, включть карту, снять вывод в терминал при запуске nm (можно просто в текстовый файл сохранить). Ну и заодно состояние интерфейса посмотреть:ifconfig
А то так гадать можно целую вечность, чего nm не нравится.
А GnomePPP случаем виснет не на моменте старта демона pppd? Если да, то запустите GnomePPP от рута, просто демон pppd не пускается от юзера, прав не хватает.