Can you please elaborate on this a little? Thats not much to go on.
What type of Mac do you have? are you using built-in bluetooth, or an adapter?
What "pref surgery" have you tried? What bluetooth programs, devices or addons are you using?
g4 pbook syncing w/treo 650 via usb -- was fixed before by deleting palm prefs (apple.plist...) and rebooting --
Perhaps the Palm sync software is trying to take control of the Bluetooth? What version of Palm Desktop are you running? Have you tried updating to the latest version.

You may also want to try running a Bluetooth Firmware update from /Applications/Utilities