This applies to (at least) the original aluminum Apple Wireless Keyboard, Model A1255 - the 4.5V model from 2007 that uses three batteries.  My controller, per lsusb, is a Broadcom Corp. BCM20702A0 Bluetooth 4.0 (0a5c:21e8).

I have found that it is difficult to pair, and even more difficult to connect.  Sometimes it will work after one or two attempts, and other times it can take dozens of tries.  Sometimes it will never work until I reboot.

I'm currently using Fedora 20 Beta, with kernel 3.11.10-300.fc20.x86_64, and the following bluez versions:

bluez-5.11-1.fc20.x86_64
bluez-libs-5.11-1.fc20.x86_64
bluez-cups-5.11-1.fc20.x86_64
bluez-hid2hci-5.11-1.fc20.x86_64

It's almost impossible to pair/connect using the Gnome Shell GUI tools.  Sometimes the BT devices pane will attempt to pair without asking for a PIN, then fail.  Sometimes it will ask me to enter a PIN, then fail.  Sometimes it will fail immediately, and other times after a timeout.  A few times, it has asked me to enter the PIN '123456' and then it will fail to connect to the device named 'Foobar.'  Ha.

Even following a pairing/connection failure in the GUI, the keyboard will sometimes, not always, show up in the Bluetooth settings panel as a known device, with the Connection switch flipped ON and grayed out, but non-functional.

So the GUI having failed, we move on to the command line.  Here is a sample bluetoothctl transcript, in which it takes two attempts to pair and four attempts to connect.  This is actually on the LOW end of attempts.  I have had it reject pairing over and over and over, and sometimes it will never connect.

[NEW] Controller 00:02:72:33:87:F6 omnipotus [default]
Agent registered
[bluetooth]# show
Controller 00:02:72:33:87:F6
	Name: omnipotus
	Alias: omnipotus
	Class: 0x1c0104
	Powered: yes
	Discoverable: no
	Pairable: yes
	UUID: PnP Information           (00001200-0000-1000-8000-00805f9b34fb)
	UUID: Generic Access Profile    (00001800-0000-1000-8000-00805f9b34fb)
	UUID: Generic Attribute Profile (00001801-0000-1000-8000-00805f9b34fb)
	UUID: A/V Remote Control        (0000110e-0000-1000-8000-00805f9b34fb)
	UUID: A/V Remote Control Target (0000110c-0000-1000-8000-00805f9b34fb)
	UUID: Phonebook Access Server   (0000112f-0000-1000-8000-00805f9b34fb)
	UUID: OBEX File Transfer        (00001106-0000-1000-8000-00805f9b34fb)
	UUID: OBEX Object Push          (00001105-0000-1000-8000-00805f9b34fb)
	UUID: Audio Source              (0000110a-0000-1000-8000-00805f9b34fb)
	UUID: Audio Sink                (0000110b-0000-1000-8000-00805f9b34fb)
	Modalias: usb:v1D6Bp0246d050B
	Discovering: no
[bluetooth]# discoverable on
Changing discoverable on succeeded
[CHG] Controller 00:02:72:33:87:F6 Discoverable: yes
[bluetooth]# scan on
Discovery started
[CHG] Controller 00:02:72:33:87:F6 Discovering: yes
[NEW] Device 00:1B:63:FA:84:9B Apple Wireless Keyboard
[bluetooth]# pair 00:1B:63:FA:84:9B 
Attempting to pair with 00:1B:63:FA:84:9B
[agent] PIN code: 399796
Failed to pair: org.bluez.Error.AuthenticationCanceled
[CHG] Device 00:1B:63:FA:84:9B Connected: no
[CHG] Device 00:1B:63:FA:84:9B Connected: yes
[bluetooth]# pair 00:1B:63:FA:84:9B 
Attempting to pair with 00:1B:63:FA:84:9B
[agent] PIN code: 999323
[CHG] Device 00:1B:63:FA:84:9B Connected: no
[CHG] Device 00:1B:63:FA:84:9B Paired: yes
Pairing successful
[bluetooth]# trust 00:1B:63:FA:84:9B 
[CHG] Device 00:1B:63:FA:84:9B Trusted: yes
Changing 00:1B:63:FA:84:9B trust succeeded
[bluetooth]# connect 00:1B:63:FA:84:9B 
Attempting to connect to 00:1B:63:FA:84:9B
Failed to connect: org.bluez.Error.Failed
[bluetooth]# connect 00:1B:63:FA:84:9B 
Attempting to connect to 00:1B:63:FA:84:9B
Failed to connect: org.bluez.Error.Failed
[CHG] Device 00:1B:63:FA:84:9B LegacyPairing: yes
[CHG] Device 00:1B:63:FA:84:9B RSSI: -62
[CHG] Device 00:1B:63:FA:84:9B Connected: yes
[CHG] Device 00:1B:63:FA:84:9B Connected: no
[CHG] Device 00:1B:63:FA:84:9B Connected: yes
[CHG] Device 00:1B:63:FA:84:9B Connected: no
[bluetooth]# connect 00:1B:63:FA:84:9B 
Attempting to connect to 00:1B:63:FA:84:9B
Failed to connect: org.bluez.Error.Failed
[bluetooth]# connect 00:1B:63:FA:84:9B 
Attempting to connect to 00:1B:63:FA:84:9B
[CHG] Device 00:1B:63:FA:84:9B Connected: yes
[CHG] Device 00:1B:63:FA:84:9B Modalias: usb:v05ACp022Cd0136
[CHG] Device 00:1B:63:FA:84:9B Modalias: usb:v05ACp022Cd0136
[CHG] Device 00:1B:63:FA:84:9B UUIDs has unsupported type
Connection successful
[bluetooth]# xyz test test
Invalid command
[bluetooth]# info 00:1B:63:FA:84:9B 
Device 00:1B:63:FA:84:9B
	Name: Apple Wireless Keyboard
	Alias: Apple Wireless Keyboard
	Class: 0x002540
	Icon: input-keyboard
	Paired: yes
	Trusted: yes
	Blocked: no
	Connected: yes
	LegacyPairing: no
	UUID: Human Interface Device... (00001124-0000-1000-8000-00805f9b34fb)
	UUID: PnP Information           (00001200-0000-1000-8000-00805f9b34fb)
	Modalias: usb:v05ACp022Cd0136
[bluetooth]# exit
[DEL] Controller 00:02:72:33:87:F6 omnipotus [default]

On the first pairing attempt, the org.bluez.Error.AuthenticationCanceled error popped up right away - there's no time for me to have entered the PIN.

The second pairing attempt succeeded.  Following that, it took four attempts to connect.

The "xyz test test" above is my test of the BT keyboard - once it connects successfully, it works fine for as long as the PC remains on, and it shows up in the Gnome BT settings as paired and connected.

Prior to a few months ago, this has always worked fine.  I think it was in F19 when I started having problems, possibly with Kernel 3.11.

From a cold boot, it never seems to automatically reconnect at the GDM login screen, as it should (and previously did).  Once I log in to my user account with a USB keyboard, it will often (eventually) reconnect, sometimes after the BT icon in the shell statusbar blinks on and off a couple of times.  This used to work fine - hit a key at GDM to wake up the keyboard and get it connected, and in 5-10 seconds it would work to enter my password.  That's no longer the case.  Here's what it looks like in dmesg:

[  102.577189] Bluetooth: RFCOMM TTY layer initialized
[  102.577213] Bluetooth: RFCOMM socket layer initialized
[  102.577215] Bluetooth: RFCOMM ver 1.11
[  113.154497] Bluetooth: re-auth of legacy device is not possible.
[  113.206606] Bluetooth: HIDP (Human Interface Emulation) ver 1.2
[  113.206620] Bluetooth: HIDP socket layer initialized
[  113.207709] apple 0005:05AC:022C.0004: unknown main item tag 0x0
[  118.207196] input: Apple Wireless Keyboard as /devices/pci0000:00/0000:00:1d.1/usb7/7-1/7-1:1.0/bluetooth/hci0/hci0:11/input13
[  118.208887] apple 0005:05AC:022C.0004: input,hidraw3: BLUETOOTH HID v1.36 Keyboard [Apple Wireless Keyboard] on 00:02:72:33:87:f6
[  145.178595] Bluetooth: re-auth of legacy device is not possible.
[  145.266687] apple 0005:05AC:022C.0005: unknown main item tag 0x0
[  145.309730] input: Apple Wireless Keyboard as /devices/pci0000:00/0000:00:1d.1/usb7/7-1/7-1:1.0/bluetooth/hci0/hci0:12/input14
[  145.310845] apple 0005:05AC:022C.0005: input,hidraw3: BLUETOOTH HID v1.36 Keyboard [Apple Wireless Keyboard] on 00:02:72:33:87:f6

(The first attempts are at 102 seconds because I sat at the GDM login prompt for a while, hitting keys and waiting for the keyboard to be recognized, to no avail.  I'm booting from an SSD so the actual boot process takes 20 seconds or so.)

I don't know why the same device is showing up in dmesg as input13 AND input14.  A look at /proc/bus/input/devices includes this:

I: Bus=0005 Vendor=05ac Product=022c Version=0136
N: Name="Apple Wireless Keyboard"
P: Phys=00:02:72:33:87:f6
S: Sysfs=/devices/pci0000:00/0000:00:1d.1/usb7/7-1/7-1:1.0/bluetooth/hci0/hci0:12/input14
U: Uniq=00:1b:63:fa:84:9b
H: Handlers=sysrq kbd event13 
B: PROP=0
B: EV=120013
B: KEY=10000 0 0 0 1007b00011007 ff9f217ac14057ff ffbeffdfffefffff fffffffffffffffe
B: MSC=10
B: LED=1f

I'm willing to help debug this; please let me know what further information I can provide.