La verdad es que yo no he tenido problemas a la hora de usar el BT con mi PDA ni con mi móvil. Emergí kdebluetooth con las bluez-libs y bluez-utils, le di el soporte en el kernel (como en todos los how-to's) y me acepta mi SE-T610 sin problemas (pin: 0000). Comprueba la configuración si acaso, no se me ocurre otra cosa.
Saludos.