Suddenly I couldn't get my iPhone tethering working (after a strange crash). To troubleshoot, I tried to delete the bluetooth connections on both my iPhone and my Macbook Pro, but even after several attempts it failed somehow. The iPhone could connect to the Mac - the internet tethering was flashing blue and the menu item on the Mac indicated that there was connection, but there was no Bluetooth PAN-connection to be seen in the System preferences. I even ran a Yasu to delete caches that could be corrupted.

A final try to delete the following preference files did it:

bluetootherror.png

They may have been both from the users Library/Preferences, but could also be from the /Library/Preferences or /System/Library/Preferences. (I forgot.) I am not sure
After a reboot, the Bluetooth PAN showed up as magic in the System Preferences Network Preference Pane and I didn't even have to re-enable it.