Troubleshooting
To retrieve useful information, the best starting point is to run blueman-applet from a Terminal window. It needs to be shut down, since only one instance may be running. You should always be able to do that with killall blueman-applet.
There will be plenty of output in the Terminal window, also including messages from blueman-manager. If you're unsure how to get behind a given problem, please provide the full output in your error report.
Test if your device is recognized by BlueZ using bluez-test-adapater list (BlueZ 4) or bluetoothctl list (BlueZ 5).
If not, you either have some hardware killswitch enabled or the device is not supported by the Linux bluetooth stack. To check the later, you can find the hardware ID with lsusb or lspci depending on the interface to google for it.