I had a similiar issue recently. While mouse and keyboard would pair to my MacBook Pro, they did not work at all. Removing both devices from SystemPreferences "Bluetooth". Resetting the PRAM and SMC of my Mac and finally adding mouse and keyboard again as new devices solved the issue.
My logfile read:
10.04.12 18:03:49,000 kernel: REQUIRE failure: inDataSize >= bytesToSend - file: /SourceCache/IOBluetoothFamily/IOBluetoothFamily-4030.4.12/Core/Family/HCI/IOBluetoothHCIController.cpp:9778
10.04.12 18:03:49,000 kernel: REQUIRE failure: inDataSize >= bytesToSend - file: /SourceCache/IOBluetoothFamily/IOBluetoothFamily-4030.4.12/Core/Family/HCI/IOBluetoothHCIController.cpp:9778
10.04.12 18:03:49,000 kernel: REQUIRE failure: destinationDevice != NULL - file: /SourceCache/IOBluetoothFamily/IOBluetoothFamily-4030.4.12/Core/Family/HCI/IOBluetoothHCIController.cpp:9754
10.04.12 18:03:49,000 kernel: REQUIRE failure: destinationDevice != NULL - file: /SourceCache/IOBluetoothFamily/IOBluetoothFamily-4030.4.12/Core/Family/HCI/IOBluetoothHCIController.cpp:9754
10.04.12 18:03:57,000 kernel: IOBluetoothL2CAPSignalChannel::parseSignal invalid signal size
10.04.12 18:03:57,000 kernel: REQUIRE failure: inDataSize >= bytesToSend - file: /SourceCache/IOBluetoothFamily/IOBluetoothFamily-4030.4.12/Core/Family/HCI/IOBluetoothHCIController.cpp:9778
10.04.12 18:04:11,000 kernel: REQUIRE failure: inDataSize >= bytesToSend - file: /SourceCache/IOBluetoothFamily/IOBluetoothFamily-4030.4.12/Core/Family/HCI/IOBluetoothHCIController.cpp:9778
10.04.12 18:04:37,000 kernel: [AppleBluetoothHIDKeyboard][handleStart] staticPrepControlChannelAction returned error e00002c0
10.04.12 18:04:37,000 kernel: [AppleBluetoothHIDKeyboard][handleStart] calling staticWillTerminateAction().
10.04.12 18:04:37,000 kernel: [AppleBluetoothHIDKeyboard][handleStart] Failed.