Comment 2 for bug 1489651

So after some investigation, I found out that this is a known problem that occurs with GDM and Pulseaudio. Basically it seems that GDM starts a pulseaudio instance and it "captures" the bluetooth a2dp sink. Unfortunately from what I could gather from some forums and some mailing lists, nobody seems to consider this a proper bug.

I've seen three workarounds:
1) Stop GDM from starting a pulseaudio instance.
2) Disable the pulseaudio bluetooth discovery module and load it after starting the user session.
3) Use another display manager, for example lightdm

I have chosen the second option, disabling 'module-bluetooth-discover' in /etc/pulse/default.pa and then running 'pacmd load-module module-bluetooth-discover && pacmd load-module module-switch-on-connect' in a terminal after I start GNOME.

Some references:
https://bbs.archlinux.org/viewtopic.php?pid=1526534#p1526534
https://wiki.archlinux.org/index.php/Bluetooth_headset#Connecting_works.2C_but_I_cannot_play_sound
https://wiki.debian.org/BluetoothUser/a2dp