This is an old problem - solutions are suggested here https://discussions.apple.com/thread/2065675?start=0&tstart=0
I created the problem exactly as you did. I was trying to fix a tethering issue and deleted the Bluetooth PAN interface and then found that contrary to normal Apple procedures, it was no longer available.
The solutions given in the link, basically, by deleting preferences files, force the System to rebuild and reinstall the Bluetooth PAN interface. However, though I got this to work, I'm not exactly sure what did it.
I tried deleting the NetworkInterfaces.plist file (see Spankymonkey) and rebooting; and then deleting the preferences.plist file (see MacMan96) and rebooting, but neither worked. I then deleted com.apple.Bluetooth.plist AND NetworkInterfaces.plist as per Spankymonkey's full solution (I couldn't find any of the other com.apple.etc files that he lists), rebooted, and it worked. I suspect the com.apple.Bluetooth.plist file might do the full job alone, if anyone wants to trial that!
Message was edited by: Ruadh2