Тебя спасет Blueman !
Вот ссылка
https://edge.launchpad.net/~blueman/+archive/ppa/+packages , скачай и установи пакеты "blueman..." из списка Source.
Потом заходишь Система-Параметры-Менеджер устройств Bluetooth, откроется сама утилита Blueman'a. Нажимаешь кнопку "Найти", будет поиск устройств (блютуз в телефоне должен быть вкл и видим), далее по шагам делаешь сопряжение и по ходу в зависимости от модели телефона выбираешь для сопряжения "Точка доступа" или "Serial port" - для конечного эффекта разницы нет.
Когда тел снюхается с компом окончательно, он появится в списке сопряженных устройств в окне Blueman'a. Щелкаешь по нему правой копкой мыши, выбираешь "Доступ к сети" или "Последовательные порты", далее соединяешься и все!
Да, перед этим в Network Manager'e надо создать соединение в закладке "Мобильные широкополосные", там в несколько кликов все легко ставится (для Билайн, МТС, Мегафон и пр.)