Defina explicitamente o pin como 0000 ou qualquer que seja o mouse antes de iniciar a pesquisa, então você poderá continuar.
Se clicar no ícone do bluetooth na barra de notificação mostrar um mouse Bluetooth, clique nessa entrada e, se estiver conectado, desconecte-o. Desconecte a bateria do mouse. Em seguida, repita o ícone clique e clique em conectar e repita mais uma vez clicando em conectar. Em seguida, conecte a bateria do mouse e ela deve iniciar o emparelhamento. Às vezes, há um pequeno botão no mouse para o emparelhamento também, mas a desconexão da bateria parece funcionar melhor para mim.
Confirme se os módulos btusb e bluetooth estão presentes quando você executa
lsmod
Quando você olha para as configurações do bluetooth, o mouse está conectado, mas não está emparelhado? Isto é o que eu vejo com meu mouse bluetooth funcionando. Aqui está um heads up para você, 12.10 tem problemas mais sérios com mouses bluetooth do que com o 12.04. Meu mouse de trabalho no mouse 12.04 perde sua informação de movimento para algo na barra de notificação, provavelmente o indicador de bateria que adicionou o mouse bluetooth em 12.10. Nunca qualquer problema em 12.04, e ele ainda se conecta muito bem em 12.10, simplesmente não funciona até que eu mate a barra de notificação. Tente remover outros dispositivos USB, tente outra porta USB (troque as pilhas do mouse?).