Погугли программку под названием blueman. Самый лучший и функциональный блютуз менеджер, который я когда-либо юзал, с помощью которого сможешь подключатся к инету через телефон посредством стандартного апплета Network Managerhttps://launchpad.net/blueman вот он
Была аналогичная проблема, когда мигрировал с 8.10 на 9.04.м Просто добавил не тот репозиторий, и в результате скачал блюмэн не той версии, который вёл себя аналогично. Советую проверить репозиторий, возможно написан не правильно. С него один раз через apt-get вытянуть пакет, а потом уже вытянуть его из кэша, и пользоватся