Apple wireless keyboard pairs but won't connect in 15.10

I have an Apple Wireless Keyboard and Trackpad (2 AA battery version of both, not the latest models that charge via a lightning cable), running Ubuntu 15.10 64-bit on an Intel NUC6i5SYK, kernel 4.2.0-27 (stock). I've got the Wireless Trackpad working fine with no issues. However, I can't for the life of me get the keyboard working. I've followed several guides and have managed to pair this keyboard via bluetoothctl, entering the PIN and seeing successfully paired. But it simply won't connect... it's paired but won't connect.

I do see the following error using journalctl:

Authentication attempt without agent
Access denied:  org.bluez.Error.Rejected

The same keyboard works flawlessly in Windows 10, so I know it's not the Bluetooth controller or keyboard itself. The trackpad also works in Windows 10, and I used this trick to copy the bluetooth keys from the Windows registry to the bluetooth configuration in Linux: How can I avoid having to pair my bluetooth mouse all the time? https://superuser.com/questions/229930/finding-bluetooth-link-key-in-windows-7-to-double-pair-a-device-on-dualboot-com

Again, the trackpad works without issues in both Windows and Linux using this approach of mirroring the Bluetooth key. Even forgetting the goal of pairing the keyboard in both Windows and Linux, and setting up the keyboard with a new pairing, the keyboard won't pair via the GUI interface. I had to use bluetoothctl and even that wasn't reliable.

Are there known issues with Bluetooth drivers in 4.2, or perhaps a bug with the Apple Wireless Keyboard specifically?

This was a pain in the button to get working. I really wanted to make a precise answer but I think the tech is a little flaky and the tools are a little trying. I did it once successfully, went to do it again from my notes to make sure my answer was sound and it took me another hour of trying to get it to take. These are the steps I followed on Ubuntu 16.04 (derived from @phireph0x and @danielfbm's answers).

1. Install bluetoothctl:

    sudo apt install bluetoothctl
   

2. Run bluetoothctl. You should see an initial list of connected devices like so:

   [NEW] Controller 23:34:17:64:AF:0E ChromeLinux_A00F [default]
   [NEW] Device 00:19:32:D3:38:01 Pico the Keyboard
   

   It's ok if you don't see the Apple keyboard initially. You should see it by the end of step 5 in the next section.

The remaining steps are from the bluetoothctl command prompt:

1. Set the agent:

   agent KeyboardDisplay
   default-agent
   

2. Turn off the Bluetooth keyboard by removing the batteries. Hold the power button in and wait 10 seconds.
3. Scan for devices: scan on.
4. Turn on the Bluetooth keyboard by reinserting the batteries holding the power button in for 10 seconds. If you don't see the keyboard power light blinking continuously, it's not trying to pair. Try again.
5. Wait for your Bluetooth keyboard to appear in bluetoothctl. This will happen asynchronously while you wait at the prompt. My keyboard popped up after 20-30 seconds.
6. Remove any previous attempts: remove 00:19:32:D3:38:01. Replace 00:19:32:D3:38:01 with your keyboard that popped up in step 5.
7. Wait for your Bluetooth keyboard to pop up again. This will probably take 20-30 seconds.
8. Make a connection and pair the Bluetooth keyboard: connect 00:19:32:D3:38:01. Replace 00:19:32:D3:38:01 with your keyboard that popped up in step 5 and 7.
9. If you're on track, you should see your prompt change from: [bluetooth]# to [Pico the keyboard]: .
10. Now, on your Bluetooth keyboard, type 1234 and press enter. That's five keystrokes on the Bluetooth keyboard: 1, 2, 3, 4, and the carriage return.
11. If that worked, you should see the prompt change to:

    [agent] Enter the pin code:
    

12. On your other keyboard, not your Bluetooth keyboard, type 1234 and press enter.

If all works well, you should see Connection successful. If the connection failed, turn off the keyboard and try again from step 2.

Troubleshooting:

• The keyboard seems to mate for life and will try to pair with any Macs it has paired with in the past. Make sure they're off.
• Restart your PC if all else fails. I was surprised to find that I didn't seem to have much trouble with the Ubuntu Bluetooth stack. I did restart a couple times but I don't think it's what got things working in the end.

I solved the problem in a similar way compared to phireph0x, but whenever I tried to use:

pair [dev]

This would give me an authentication error. So I restarted the whole process from the beginning and this time instead of using pair, I used:

connect [dev]

Next thing was input the PIN in my computer, and then type the same PIN in the keyboard. Worked like a charm. I am now using the bluetooth keyboard!

It is also worth trying to setup the agent before connecting (also inside the bluetoothctl):

agent KeyboardDisplay
default-agent