Comment 31 for bug 318465

Updated workaround instructions:
Mouse:
1) Connect backup keyboard (required!) and optionally backup mouse
2) Start System/Preferences/Bluetooth Manager or blueman-manager. Alt-F1 helps if you don't have a backup mouse.
3) Activate "Search" on the toolbar so that the mouse appears. Moving the mouse or hitting the red connect button may help here. Several attempts may be required before it shows up.
4) Select your mouse in the list of devices, then hit space so it's highlighted.
5) Activate the keys, aka "create pairing". It will ask you to type in a PIN, for which you will use "0000". This is the part that requires a backup keyboard.
6) Activate "Setup" on the toolbar. With "Input Service" selected (the default) hit forward.
7) Your mouse should now work.
8) You can also mark it as trusted, the little yellow plus-ish thing. I'm not sure what effect this has. I activate it to be on the safe side.

Keyboard:
1) Connect backup mouse and/or backup keyboard.
2) Start System/Preferences/Bluetooth Manager or blueman-manager.
3) Activate "Search" on the toolbar so that the keyboard appears. Hitting keys or the red connect button may help here. Several attempts may be required before it shows up.
4) Click on your keyboard to highlight it.
5) Do not click on the keys. Instead, activate "Setup". With "Use Random Passkey" selected hit forward.
6) A PIN will be shown on the screen. Wait for your keyboard's LCD screen to ask for a passkey, then enter the PIN on the keypad and hit Enter.
7) Wait until the failure to connect is reported, then close this window.
8) Activate "Setup" again. This time with "Input Service" selected (the default) hit forward again.
9) Your keyboard should now work.
10) Again I don't know what effect trusted has. I activate it to be on the safe side.

Obviously that's pretty involved for what should be almost or completely automatic.
1) Hitting the red buttons should be sufficient for a temporary connection, and should prompt if a more permanent connection is desired.
2) The installer and upgrader should detect the keyboard/mouse in HID mode and automatically add a permanent connection.

IMO, as this makes an installation unusable (until they find this bug report and implement the workaround) it's worth more than a Low priority.