Well to start with, what Bluetooth hardware does the machine have? Is it detected by the kernel? Almost all USB or on-board Bluetooth devices are supported in a modern kernel, but there are some exceptions.
To see if the hardware and drivers are working you can start with something simple like scanning for other devices. Put your phone into discoverable mode and then run the following on the computer:
You should see your phone's name and MAC pop up there after a few seconds. If you don't see anything, or if you get an error, then you know that either the hardware/drivers are not setup properly, or there is a BlueZ problem.
If that works, then you should be able to proceed with the standard GNOME Bluetooth management tools. You don't mention if you got this far, or if there was even a problem at all for that matter, so it is hard to give any more specific advice without more information.