Every device and Bluetooth desktop driver is different and has different UI.
Please post any device/driver specific tips you have learned here.
I was able to connect using these steps with Sprint HTC Touch Diamond, HTC S620 Exaclibur, and Motorola Q9h.