As the first step in trouble shooting the problem, I decided to go back to a stock ROM since that has seemed to work for others. I deleted all of my user data and formatted system, cache, data and davlik cache before each ROM load. I first tried the stock Gingerbread ROM but the Bluetooth was still not working consistently. I then tried the ICS stock ROM but again the bluetooth did not work correctly. On each ROM, I tested the bluetooth thoroughly by power cycling the phone, using airplane mode, and trying to toggle bluetooth repeatedly. I was able to turn the bluetooth on in each ROM but it would only come on about 10% of the time and there did not appear to be a pattern of reboots or software manipulation that I could do which would cause it to turn on. Nothing seem to work so I suspected there must be a hardware problem.
I opened up the phone tonight and on a hunch, I reseated the antenna (the white antenna on the right side of the phone when it's laying on its face) by removing it and reattaching it to the board by the two ends of the antenna but did not remove it from the middle clip. I'm not sure what happened, but when I restarted, I had no wireless service which made me think I was buying a new phone tomorrow but the bluetooth was working every time! I opened the phone back up and totally removed the antenna and reseated it. This time when the phone started, I had great wireless signal and the bluetooth worked perfectly. Granted, it's only been a few hours but it's never worked so consistently since I reseated the antenna. No idea if this will last but it seems like in my case, there was an issue with the connection to the antenna. I'm not even sure if that antenna is used for the bluetooth or not.
If this works for the next couple of days, I might try buying a new antenna. If you decide to remove the antenna, make sure that you use a needle nose pliers to remove the two ends of the antenna. You do not want to pull the antenna off by the wire. Also, if you reseat it, make sure there is equal slack on each side from the middle clip because the antenna needs to fit between the two golden lines printed on the case. Otherwise, when you put the case together, it will pinch the antenna. As with all hardware changes, THERE IS A CHANCE THAT THIS WILL SERIOUSLY DAMAGE THE PHONE'S ABILITY TO RECEIVE WIRELESS SIGNAL. I thought for a few minutes I would be at T Mobile tomorrow buying a replacement.
I'll report back if this works long term. Sorry if someone already mentioned this as a solution. I did quite a bit of searching and had never heard of someone trying this.