Well in 8.04 I used Blueman to connect bluetooth devices. This should still work ok you just need to install it first.
These instructions are straight from the Blueman web page:
First, open a terminal window (Applications->Accessories->Terminal). Then add the repository's key to your system's list of trusted APT keys by copy and pasting the following:
Next, add the repository to your system's list of APT sources:
wget -q http://download.tuxfamily.org/blueman/blueman.gpg -O- | sudo apt-key add -
Then update APT's package information by running
sudo wget http://download.tuxfamily.org/blueman/hardy.list -O /etc/apt/sources.list.d/blueman.list
Now you can install blueman by clicking this link. Alternatively, you can install by going to System->administration->Synaptic and searching for blueman.
sudo apt-get update
Once it is installed open the program by going to Applications > Accessories > Blueman Bluetooth Manager. Make your device discoverable and then click on the Inquiry button (if your mouse/keyboard doesn't show up click it again).
After your device shows, in the menu click Edit > Services and make sure for Input Status has a green check mark and Autostart has a check mark. Next in the Services window click on the Configure button and select Add New Input Device. For the address click on the drop down menu and your device should be listed, select it and click on add. It will ask you some questions about authorized and trusted, make it both.
And that should do it. Do this for both your keyboard and mouse and if you make the right selections for favorites and trusted it should remember the devices every time you boot your computer.
Let me know if this works for you. A lot of it had to come from memory.