You might want to check the software on the phone. Also verify that Bluetooth is set to always on. After reading your thread, it reminded me of something similar from someone else and they mentioned Cingular RAZR as well.

Also you can stop by your local carrier and ask them for help. Typically they will let you try other phones. It might be something flakey with that phone