Then a friend mentioned that you had to reset the PRAM. Well, command-Option-P-R doesn't work on my laptop (it has open firmware with the password set). I discovered I had to reboot with Command-Option-O-F (to boot into open firmware), type in my firmware password (you have one of those on your laptop, don't you?), and type reset, hit Enter, then type reset-all, and hit Enter again.
Hey presto, my Bluetooth is back. Whew. Oh and I forgot to mention, when I tried to reboot after the FireWire trick, my laptop wouldn't boot. It wanted the FireWire disk. You have to hold down Option while it's booting up to look for another disk (or reset the PRAM).

