Когда на моем ноутбуке стояла Ubuntu 7.10, а потом и 8.04, выход в Интернет через bluetooth+gprs я настраивал, пользуясь этим руководством.
После обновления системы до 8.10 у меня (как и у многих, если судить по сообщениям в различных форумах) возникли некоторые сложности с подключением через Bluetooth.