Este é apenas um trabalho temporário:
O problema parece ser algum conflito de software que sobrecarrega ou desabilita o software Bluetooth Bluez na inicialização. Atualmente, estou reinstalando manualmente o Bluez através do Synaptic toda vez que o problema ocorre.
Eu suspeito que uma correção permanente envolve identificar o software conflitante e substituí-lo / removê-lo ou fazer alguma edição na ordem em que os programas são carregados na inicialização.