I had a 1$ bluetooth dongle laying around, and since it didn't work in Unity and I've switched to GNOME shell, I tried it today.

The dongle was recognized immediately, and didn't have any problems searching for devices. Then I tried searching for my mouse (Razer Orochi), found it, and only had to click pair and type "0000" as code.

All this was done in the native Bluetooth manager in Ubuntu, also the bluetooth dongle apparently only worked in Windows.