If I use bluetoothctl - connection is successful on first attempt.

This message is a reminder that Fedora 25 is nearing its end of life.
Approximately 4 (four) weeks from now Fedora will stop maintaining
and issuing updates for Fedora 25. It is Fedora's policy to close all
bug reports from releases that are no longer maintained. At that time
this bug will be closed as EOL if it remains open with a Fedora  'version'
of '25'.

Package Maintainer: If you wish for this bug to remain open because you
plan to fix it in a currently maintained version, simply change the 'version'
to a later Fedora version.

Thank you for reporting this issue and we are sorry that we were not
able to fix it before Fedora 25 is end of life. If you would still like
to see this bug fixed and are able to reproduce it against a later version
of Fedora, you are encouraged  change the 'version' to a later Fedora
version prior this bug is closed as described in the policy above.

Although we aim to fix as many bugs as possible during every release's
lifetime, sometimes those efforts are overtaken by events. Often a
more recent Fedora release includes newer upstream software that fixes
bugs or makes them obsolete.

This bug is in Fedora 26 and Fedora 27 too.

This message is a reminder that Fedora 27 is nearing its end of life.
On 2018-Nov-30  Fedora will stop maintaining and issuing updates for
Fedora 27. It is Fedora's policy to close all bug reports from releases
that are no longer maintained. At that time this bug will be closed as
EOL if it remains open with a Fedora  'version' of '27'.

Package Maintainer: If you wish for this bug to remain open because you
plan to fix it in a currently maintained version, simply change the 'version' 
to a later Fedora version.

Thank you for reporting this issue and we are sorry that we were not 
able to fix it before Fedora 27 is end of life. If you would still like 
to see this bug fixed and are able to reproduce it against a later version 
of Fedora, you are encouraged  change the 'version' to a later Fedora 
version prior this bug is closed as described in the policy above.

Although we aim to fix as many bugs as possible during every release's 
lifetime, sometimes those efforts are overtaken by events. Often a 
more recent Fedora release includes newer upstream software that fixes 
bugs or makes them obsolete.

Fedora 27 changed to end-of-life (EOL) status on 2018-11-30. Fedora 27 is
no longer maintained, which means that it will not receive any further
security or bug fix updates. As a result we are closing this bug.

If you can reproduce this bug against a currently maintained version of
Fedora please feel free to reopen this bug against that version. If you
are unable to reopen this bug, please file a new report against the
current release. If you experience problems, please add a comment to this
bug.

Thank you for reporting this bug and we are sorry it could not be fixed.

Still present.

This bug appears to have been reported against 'rawhide' during the Fedora 30 development cycle.
Changing version to '30.

Still present in Fedora 30 with 

 Port 3: Dev 8, If 0, Class=Wireless, Driver=btusb, 12M
                    ID 0a12:0001 Cambridge Silicon Radio, Ltd Bluetooth Dongle (HCI mode)
                |__ Port 3: Dev 8, If 1, Class=Wireless, Driver=btusb, 12M
                    ID 0a12:0001 Cambridge Silicon Radio, Ltd Bluetooth Dongle (HCI mode)

FWIW, I spent some time trying to reproduce this a couple of weeks ago, and could not see any bit of difference between how gnome-bluetooth behaves, and how bluetoothctl behaves, and I've also not been able to reproduce the problem.

Might be a hardware, driver or firmware problem for all I know.

Let us know if you get any closer to figuring out what the problem is.

I've faced this issue in Fedora 30.

In order to make it work from Gnome, I had to install the following package:

bluez-hid2hci

I'm also facing this issue in Fedora 30 on Lenovo ThinkPad T450.

My bluetooth device is Samsung Galaxy Buds.

I've received the same exact journal log error as you, either by connecting using the GUI or by using the following command:

bluetoothctl connect <paired-bluetooth-device-mac>

Moreover it doesn't work even after 15 attempts.

Here is my hardware and driver:

[eido@eido-lap-fedora ~]$ sudo lspci -v
03:00.0 Network controller: Intel Corporation Wireless 7265 (rev 99)
	Subsystem: Intel Corporation Dual Band Wireless-AC 7265
	Flags: bus master, fast devsel, latency 0, IRQ 50
	Memory at e1000000 (64-bit, non-prefetchable) [size=8K]
	Capabilities: [c8] Power Management version 3
	Capabilities: [d0] MSI: Enable+ Count=1/1 Maskable- 64bit+
	Capabilities: [40] Express Endpoint, MSI 00
	Capabilities: [100] Advanced Error Reporting
	Capabilities: [14c] Latency Tolerance Reporting
	Capabilities: [154] L1 PM Substates
	Kernel driver in use: iwlwifi
	Kernel modules: iwlwifi

My current solution is to delete paired device, pair it again, and connect to it.

I also have Dell Latitude 5580 running Ubuntu 18.04.3,
in which this issue is NOT being reproduced, and works as expected (either by using GUI or bluetoothctl connect).

The following log is for successful connect to Samsung Galaxy Buds:
(I censored device MAC address (using <MAC>) from privacy reasons).

Nov 06 17:45:24 eido-laptop-ubuntu kernel: input: <MAC> as /devices/virtual/input/input21
Nov 06 17:45:24 eido-laptop-ubuntu systemd-logind[997]: Watching system buttons on /dev/input/event21 (<MAC>)
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (II) config/udev: Adding input device <MAC> (/dev/input/event21)
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (**) <MAC>: Applying InputClass "libinput keyboard catchall"
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (II) Using input driver 'libinput' for '<MAC>'
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (II) systemd-logind: got fd for /dev/input/event21 13:85 fd 90 paused 0
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (**) <MAC>: always reports core events
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (**) Option "Device" "/dev/input/event21"
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (**) Option "_source" "server/udev"
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (II) event21 - <MAC>: is tagged by udev as: Keyboard
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (II) event21 - <MAC>: device is a keyboard
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (II) event21 - <MAC>: device removed
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (**) Option "config_info" "udev:/sys/devices/virtual/input/input21/event21"
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (II) XINPUT: Adding extended input device "<MAC>" (type: KEYBOARD, id 22)
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (**) Option "xkb_layout" "us,il"
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (**) Option "xkb_variant" ","
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (II) event21 - <MAC>: is tagged by udev as: Keyboard
Nov 06 17:45:24 eido-laptop-ubuntu /usr/lib/gdm3/gdm-x-session[1661]: (II) event21 - <MAC>: device is a keyboard
Nov 06 17:45:27 eido-laptop-ubuntu bluetoothd[993]: /org/bluez/hci0/dev_<MAC>/fd0: fd(36) ready
Nov 06 17:45:27 eido-laptop-ubuntu rtkit-daemon[1351]: Supervising 6 threads of 1 processes of 1 users.
Nov 06 17:45:27 eido-laptop-ubuntu rtkit-daemon[1351]: Successfully made thread 6383 of process 1846 (n/a) owned by '1000' RT at priority 5.
Nov 06 17:45:27 eido-laptop-ubuntu rtkit-daemon[1351]: Supervising 7 threads of 1 processes of 1 users.

eido@:~$ sudo lspci -v
02:00.0 Network controller: Intel Corporation Wireless 8265 / 8275 (rev 78)
	Subsystem: Intel Corporation Wireless 8265 / 8275
	Flags: bus master, fast devsel, latency 0, IRQ 131
	Memory at ed200000 (64-bit, non-prefetchable) [size=8K]
	Capabilities: [c8] Power Management version 3
	Capabilities: [d0] MSI: Enable+ Count=1/1 Maskable- 64bit+
	Capabilities: [40] Express Endpoint, MSI 00
	Capabilities: [100] Advanced Error Reporting
	Capabilities: [140] Device Serial Number 28-c6-3f-ff-ff-83-5e-9b
	Capabilities: [14c] Latency Tolerance Reporting
	Capabilities: [154] L1 PM Substates
	Kernel driver in use: iwlwifi
	Kernel modules: iwlwifi

I have updated from Fedora 30 to Fedora 31 and this issue fixed to me.

Here is how the successful connection log looks like:
(I censored device MAC address (using <MAC>) from privacy reasons).

Nov 13 17:55:41 eido-lap-fedora bluetoothd[833]: connect error: Device or resource busy (16)
Nov 13 17:55:41 eido-lap-fedora systemd[1467]: dbus-:1.2-org.gnome.Characters.BackgroundService: Succeeded.
Nov 13 17:55:44 eido-lap-fedora kernel: input: <MAC> as /devices/virtual/input/input26
Nov 13 17:55:44 eido-lap-fedora systemd-logind[983]: Watching system buttons on /dev/input/event23 (<MAC>)
Nov 13 17:55:47 eido-lap-fedora bluetoothd[833]: /org/bluez/hci0/<MAC>/fd1: fd(101) ready

I guess this is something related to bluez package?

Hi i still have the same bug on Fedora 31.
I must click several times on the button to eventually connect a bluetooth device.
I'm working on Lenovo Thinkpad T440.
I tried to install bluez-hid2hci but it still doesn't work.

Hello I also have this issue on Fedora 30/31/32. I must click on connect button about 20 times to have it connected.

Using bluetooth headphones SoundBuds Curve and connecting to the laptop Lenovo ThinkPad P50. If you want logs or anything please ask. I'll try to help.

Also having this issue for a long while, at least F29 or so. Even if my device is not currently connected to anything the GUI button will not connect easily. I have to click it over and over again while using "bluetoothctl connect ..." works the first time. 

Apr 30 10:52:40 b-wing.local kernel: Bluetooth: hci0: advertising data len corrected
Apr 30 10:52:40 b-wing.local bluetoothd[1170]: Unable to get Headset Voice gateway SDP record: Device or resource busy
Apr 30 10:52:40 b-wing.local bluetoothd[1170]: connect error: Device or resource busy (16)
Apr 30 10:52:42 b-wing.local bluetoothd[1170]: connect error: Device or resource busy (16)
Apr 30 10:52:42 b-wing.local bluetoothd[1170]: Unable to get Headset Voice gateway SDP record: Device or resource busy
Apr 30 10:52:42 b-wing.local bluetoothd[1170]: connect error: Device or resource busy (16)
Apr 30 10:52:43 b-wing.local bluetoothd[1170]: Unable to get Headset Voice gateway SDP record: Device or resource busy
Apr 30 10:52:43 b-wing.local bluetoothd[1170]: connect error: Device or resource busy (16)
Apr 30 10:52:44 b-wing.local kernel: Bluetooth: hci0: advertising data len corrected
Apr 30 10:52:45 b-wing.local kernel: Bluetooth: hci0: advertising data len corrected
Apr 30 10:52:45 b-wing.local bluetoothd[1170]: Unable to get Headset Voice gateway SDP record: Device or resource busy
Apr 30 10:52:45 b-wing.local bluetoothd[1170]: connect error: Device or resource busy (16)
Apr 30 10:52:46 b-wing.local kernel: Bluetooth: hci0: advertising data len corrected
Apr 30 10:52:46 b-wing.local bluetoothd[1170]: Unable to get Headset Voice gateway SDP record: Device or resource busy
Apr 30 10:52:46 b-wing.local bluetoothd[1170]: connect error: Device or resource busy (16)
Apr 30 10:52:46 b-wing.local kernel: Bluetooth: hci0: advertising data len corrected
Apr 30 10:52:47 b-wing.local bluetoothd[1170]: Unable to get Headset Voice gateway SDP record: Device or resource busy
Apr 30 10:52:47 b-wing.local bluetoothd[1170]: connect error: Device or resource busy (16)
Apr 30 10:52:47 b-wing.local kernel: Bluetooth: hci0: advertising data len corrected
Apr 30 10:52:47 b-wing.local bluetoothd[1170]: Unable to get Headset Voice gateway SDP record: Device or resource busy
Apr 30 10:52:47 b-wing.local bluetoothd[1170]: connect error: Device or resource busy (16)
Apr 30 10:52:51 b-wing.local systemd[1493]: Reached target Bluetooth.
Apr 30 10:52:51 b-wing.local bluetoothd[1170]: /org/bluez/hci0/dev_38_18_4C_D4_F2_31/sep1/fd0: fd(105) ready

This message is a reminder that Fedora 30 is nearing its end of life.
Fedora will stop maintaining and issuing updates for Fedora 30 on 2020-05-26.
It is Fedora's policy to close all bug reports from releases that are no longer
maintained. At that time this bug will be closed as EOL if it remains open with a
Fedora 'version' of '30'.

Package Maintainer: If you wish for this bug to remain open because you
plan to fix it in a currently maintained version, simply change the 'version' 
to a later Fedora version.

Thank you for reporting this issue and we are sorry that we were not 
able to fix it before Fedora 30 is end of life. If you would still like 
to see this bug fixed and are able to reproduce it against a later version 
of Fedora, you are encouraged  change the 'version' to a later Fedora 
version prior this bug is closed as described in the policy above.

Although we aim to fix as many bugs as possible during every release's 
lifetime, sometimes those efforts are overtaken by events. Often a 
more recent Fedora release includes newer upstream software that fixes 
bugs or makes them obsolete.

FYI, I get this same problem on Ubuntu. I was able to work around by setting:

FastConnectable = true

In /etc/bluetooth/main.conf

I am having this issue in Fedora 31. Have been since many versions ago.

I can reproduce this using bluetoothctl as well. However, it only fails 20% of the time.

```
_bt_device_name='ECANDY'
_bt_device_addr="$(bluetoothctl devices | grep "$_bt_device_name" | cut -d' ' -f2)"
[ -n "$_bt_device_addr" ] && bluetoothctl info "$_bt_device_addr" >/dev/null 2>&1 && {
    bluetoothctl disconnect "$_bt_device_addr"
    sleep 1s
    attempts=0
    while [ true ]; do
        (( attempts++ ))
        bluetoothctl connect "$_bt_device_addr" && break
    done
    echo "Took $attempts attempts."
}

```

I had originally thought that this had something to do with the scan operation but I am not so sure. So maybe it is controller specific or device type specific? Or a combination?

I'm still getting the same problem after upgrading to F32 (on my Thinkpad T440).
I tried on a live iso but once again the issue was here.
I also tried on a ubuntu live iso and the issue was gone. So is there any difference between Fedora's and Ubuntu's bluetooth management ?
I can assure you I don't have any issues when I'm using an external bluetooth adaptater.
I can provide logs if needed.

I am also experiencing this bug on a Thinkpad E495 with a (self-installed) Intel AX200 Bluetooth/WiFi card. This issue also occurred on my previous HP laptop (older generation Intel WiFi) across the last few Fedora releases, but I did not see it with the E495's original Bluetooh/WiFi card (that, however, would lose internet connectivity whenever a bluetooth device was connected).

I confirm that the "FastConnectable" setting works for me too. Without this option, the problem mostly happens when connecting to another BT device than the one the host was previously connected with, hence requiring an action in the gnome control center GUI. Reconnecting to the previous device is automatic else.

When it fails:

< HCI Command: Create Connection (0x01|0x0005) plen 13      #44 [hci0] 5.358804
        Address: A0:60:90:0B:B1:E6 (Samsung Electronics Co.,Ltd)
        Packet type: 0xcc18
          DM1 may be used
          DH1 may be used
          DM3 may be used
          DH3 may be used
          DM5 may be used
          DH5 may be used
        Page scan repetition mode: R2 (0x02)
        Page scan mode: Mandatory (0x00)
        Clock offset: 0x0000
        Role switch: Allow slave (0x01)
> HCI Event: Command Status (0x0f) plen 4                   #45 [hci0] 5.359453
      Create Connection (0x01|0x0005) ncmd 1
        Status: Success (0x00)
> HCI Event: Connect Complete (0x03) plen 11                #46 [hci0] 5.360398
        Status: Command Disallowed (0x0c)
        Handle: 65535
        Address: A0:60:90:0B:B1:E6 (Samsung Electronics Co.,Ltd)
        Link type: ACL (0x01)
        Encryption: Disabled (0x00)

When it works:

< HCI Command: Create Connection (0x01|0x0005) plen 13    #212 [hci0] 20.527371
        Address: A0:60:90:0B:B1:E6 (Samsung Electronics Co.,Ltd)
        Packet type: 0xcc18
          DM1 may be used
          DH1 may be used
          DM3 may be used
          DH3 may be used
          DM5 may be used
          DH5 may be used
        Page scan repetition mode: R2 (0x02)
        Page scan mode: Mandatory (0x00)
        Clock offset: 0x0000
        Role switch: Allow slave (0x01)
> HCI Event: Command Status (0x0f) plen 4                 #213 [hci0] 20.527859
      Create Connection (0x01|0x0005) ncmd 1
        Status: Success (0x00)
> HCI Event: Vendor (0xff) plen 4                         #214 [hci0] 20.836922
      Intel PTT Switch Notification (0x26)
        Handle: 256
        Packet type table: Enhanced data rate (0x01)
> HCI Event: Connect Complete (0x03) plen 11              #215 [hci0] 20.840929
        Status: Success (0x00)
        Handle: 256
        Address: A0:60:90:0B:B1:E6 (Samsung Electronics Co.,Ltd)
        Link type: ACL (0x01)
        Encryption: Disabled (0x00)

I also must click on connect button about 20 times to have it connected. Afects me since fedora 30.

Same problem here:
Speakers Bose Soundtouch.
gnome-bluetooth-3.34.1-1.fc31
bluez-5.54-1.fc31

Why is this problem reported since 2016 and not touched by developers?
Please answer something, do you need logs or anything?

Upstream report:
https://gitlab.gnome.org/GNOME/gnome-control-center/-/issues/820

The needinfo request[s] on this closed bug have been removed as they have been unresolved for 1000 days