Este mensaje me ha aparecido usando Elementary OS Linux en la versión 5.1 Hera cuando he intentado conectar un teclado bluetooth de la marca SUBBLIM que ya tenía previamente emparejado y con el que ya había estado trabajando antes sin problemas. No he encontrado el origen del error, pero como ya se había conectado sin problemas antes, pensé que eliminando el dispositivo de la lista de emparejados y volviendo a empezar podría solucionarse.
Dado que la interfaz de configuración de bluetooth en ElementaryOS no permite hacer mucho, esto solo puede hacerse mediante la consola. Para ello tienen que estar instalados los paquetes bluez y bluez-tools. Una vez instalados ejecutamos el comando bluetoothctl, el cual abre un diálogo en consola que nos muestra una lista con los dispositivos emparejados, su MAC y un nombre descriptivo, si lo tiene.
Como el dispositivo que da el problema es el teclado, lo eliminamos de la lista con el comando remove 12:34:56:78:90:12 (reemplazando el valor de la MAC con el que nos aparece en el listado). Para salir del diálogo tecleamos exit.
A continuación, en la interfaz de configuración de bluetooth ya se puede volver a emparejar y conectar de nuevo el dispositivo.