I found a solution that seems to work for me (tentatively, haven't road tested this but works while I'm sitting here in the office):
http://www.iphoneatlas.com/2008/01/17/fix-for-iphone-113-bluetooth-problems/
"Toggle Airplane mode Turn Bluetooth off, then navigate to Settings, then slide Airplane Mode to On, wait a few seconds, then slide it back to Off. It seems that discontinuing and restarting the EDGE and WiFi components in the iPhone can restore connectivity.
iPhone Atlas reader Brian Dose, who experienced success with this workaround, writes:
“The restore option did not work for me when I tried it, however I found a way that worked for me that did not involve restoring at all. I turned the Bluetooth off. Then I went and put my Iphone into airplane mode. I then went back and reactivated the bluetooth. After picking re-enable, the bluetooth worked just fine and I didn’t have to do a restore. Hope this works for others as well.”