I can report that Andy's steps worked for me on my newly-flashed-to-Diablo N800. A reboot after you've nuked the contents of /var/lib/bluetooth/ is indeed required, but you don't have to pull the battery or go get a drink of water: just turn the tablet off and then power it right back up and carry on with his steps.

When re-pairing with my SU-8W, I found that there was an extra "Retrieving device name..." stage before it showed the keyboard in the list of pairable devices. I'm pretty sure that this is your first hint that things are working. The second hint is that it doesn't throw up "Pairing Failed" right away when you start pairing -- instead, the green "Fn" light comes on after a moment or two and then you can type in your sooper seekrit code and press Enter.

(Actually, the first hint that things are working is probably that the Bluetooth settings tool has forgotten your tablet's Bluetooth name, putting something generic in the "My device's name:" field.)