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: