Well, I'm in KDE, have a desktop with no native bluetooth, and it's been hit or miss with various hardware/software combinations.
On the software, the one that seems most mature, works best with my setup is bluedevil.
On the hardware, I've gone through a variety of usb bluetooth dongles. I think the software development has led to greater functionality and compatibility over the period of time when I've been trying to set bluetooth up with my phone. Currently, what I am using is identified after issuing 'lsusb', as root, as:
0a12:0001 Cambridge Silicon Radio, Ltd Bluetooth Dongle (HCI mode)
There are many hits at google on this string and I suspect the older reports of failure might have to do with older/various bluetooth software.
One list with this dongle on it:
http://en.opensuse.org/HCL:BluetoothIt can be hit and miss but I would go from shopping for a dongle, search for Linux compatibility, buy it, try it.
Your phone will have documentation for bluetooth pairing. Capabilities and steps to pair will vary, phone to phone.