I've found the bluetooth devices that come with a dongle which emulates a USB device to be much more useful than the ones with a dongle that is "native" bluetooth.
You don't need any bluetooth software on linux to be working at all, so there is much less source for troubles :-). If it is a keyboard, you can actually use it in the BIOS.
On the other hand, that means the dongle isn't generally useful for bluetooth connections, but is pretty much dedicated to the one device.