ふとした拍子に、キーボードの接続を削除してしまったらその後どうしても発見してくれない状態になってしまうことがあります。
根本的に解決になっているわけではないですが以下の方法で認識することが有ります。
rm -rf /var/lib/bluetooth/<番号>/cache番号には、それぞれ環境によって異なります。サービスなどを再起動すればよいのかと思いますが強制的に消してしまっているのでシステムが再起動できれば再起動してしまうほうが良いです。再起動後、機器をペアリングモードにすることで無事に接続ができたことを確認できました。