This was a very common issue with the old 6700. Both 6700's that I owned suffered from BT that would shut off or fail to start and no software fix solved the problem.
AFAIK, the HTC phones that succeeded the 6700 didn't suffer the same issue. Perhaps you have a bad BT chip in your phone? If you're still within the warranty or have insurance, maybe a trip to the local repair center for a swap is in order? Good luck, I remember how frustrating this was with the 6700 when I thought I could answer from the headset only to find it wasn't connected at all.