Comment 22 for bug 285412

I was having the same problem as zeusOne. After a bunch of investigation, it became clear that bluetoothd didn't have all the necessary dbus devices set up internally. Forcing it to do service discovery on my headphones (Plantronics 590A, in a2dp mode) made it all work:

dbus-send --system --dest=org.bluez --print-reply /org/bluez/hci0/dev_00_19_7F_38_F6_FF org.bluez.Device.DiscoverServices string:

I'm not sure why this should be necessary, or what should be doing it, but hopefully this will help someone else.