The largest problem I've had with Bluez (the bluetooth stack under Linux) is the pairing process. If everything "just works" that's great, but when your distribution lets you down and something gets miss-configured, it can be very difficult to get a phone or PDA to pair with the linux box.

Here is how to force the issue:

passkey-agent –default /usr/bin/bluez-pin (Or replace bluez-pin with your favorite PIN program) (Your bluez-pin agent might be located in a different directory which bluez-pin will find it)
hcitool scan – finds the device ID , looks something like: 00:0D:AD:B2:31:2A
hcitool cc – connects to the device

hcitool auth – Requests a passkey/pin exchange.

Enter the same PIN on the device and in the bluez-pin dialog and the computer and device should now be paired.