Ok if you are having trouble follow these steps and say what went wrong:

1) Open a terminal

2) Gain root access
$ root
or
$ sudo gainroot

3) Install the sysklogd deamon
# apt-get install sysklogd

4) Restart the bluetooth deamon
# stop bluetoothd
# start bluetoothd

5) Go to the bluetooth menu and delete the entry for the keyboard

6) Pair the keyboard to the phone (make sure they pair up ok!). If the pairing doesn't work, or in general, give it also a try with pin 0000. Some keyboards don't support anything else.

7) When the keyboard is setup in discover mode get its BT address
# hcitool scan
Scanning ...
00:5F:F6:12:26:BC Bluetooth Keyboard

8) Get the interface identifier
# dbus-send --system --print-reply --dest=org.bluez / org.bluez.Manager.DefaultAdapter
object path "/org/bluez/2685/hci0"

9) Put that all together! (make sure the keyboard is still in discover mode!) Notice
# dbus-send --system --print-reply --dest=org.bluez /org/bluez/2685/hci0/dev_00_5F_F6_12_26_BC org.bluez.Input.Connect

10) and now you should be able to get a descent error message from /var/log/syslog
# tail /var/log/syslog

Some more stuff:

If you are getting a permission denied, try creating the file (as root) /etc/bluetooth/hcid.conf with the content:
that could help.


EDIT:
Sorrry fixed some typos