Eu tive o mesmo problema agora quando estava tentando emparelhar meu lenovo z570 com meu fone de ouvido nokia bh503.
Achei impossível com o gerenciador padrão, mas instalei blueman . Você pode fazer isso através do terminal ( CTRL + ALT + T ):
sudo apt-get install blueman
ou através do Centro de Software:
Com isso instalado eu corri bluetooth manager da lista de aplicativos, usando esse gerenciador eu era capaz de emparelhar meus dispositivos sem maiores problemas (demorei alguns momentos)
Eu espero que isso resolva o seu problema também. Melhor sorte para você!