Então eu tentei seguir as instruções do Ubuntu 16.04.2 em Intel NUC7i3, Bluetooth não funciona mas não resolveu meus problemas. Pelo menos eu sei que não resolveu diretamente o meu problema
Acabei seguindo estas instruções
Como conectar fones de ouvido Bluetooth ao Laptop?
e usei bluetoothctl para remover o dispositivo salvo. Ran scan on then pair <bluetooth mac address> than connect <bluetooth mac address>
Isso funcionou para o meu mouse, mas quando tentei conectar meus fones de ouvido bluetooth JBL, não funcionou. Então não estou bem claro sobre o motivo da questão.