Desliguei e liguei a rede wireless no netbook (fisicamente, no botão de ligar e desligar wireless).. e... o bluetooth funcionou! Automagicamente.
Agradeço a todos que auxiliaram na ajuda, principalmente ao Tota. Apesar da solução ter sido algo bem diferente do que pensava, o processo de pesquisa e debug me ajudou a entender um pouco mais sobre o ubuntu.