I ran into this issue on my Lenovo P51 running Ubuntu 18.04, and I discovered that the pactl module "module-bluetooth-discover" was not loading properly at boot time. I fixed the issue by replacing it with "module-bluez5-discover" in my pulse configuration.
You can test this by running:
sudo pactl unload-module module-bluetooth-discover
sudo pactl load-module module-bluez5-discover
And try to repair/reconnect your devices. If it works, replicate the following configuration in your /etc/pulse/default.pa config.
# Modify: /etc/pulse/default.pa
# Comment out the following line
# Replace it with ...
My suspicion is that this is a change that was made during the switch from Unity to Gnome and the leftover configurations remained, leaving the standard Bluetooth modules behind which don't load correctly.
After switching to bluez5, I have since had no issues, and Bluetooth connects without complaint on my mobile phone, mouse, and headset. :)
EDIT: I also followed several steps mentioned here: Bluetooth doesn't work after resuming from sleep, Ubuntu 18.04 LTS
To exactly replicate my configuration, make sure you
apt-get install bluez blueman pulseaudio to have all the same packages. As was suggested in the referenced problem, I believe this was caused by upgrading to 18.04 from 17.04.