I experienced the problem before, but with latest updates I successfully paired with my phone. I rebooted the machine after the updates. -- Impossible to do pairing in Kubuntu https://launchpad.net/bugs/56651