Para renomear o Bluetooth, certifique-se de que o mesmo esteja ligado. E depois abra o terminal e execute o comando abaixo. (Testado em Ubuntu 14.04)

sudo hciconfig hci0 name NOME_ESCOLHIDO