The release of iOS 4.1 fixed many Bluetooth connection problems from iOS 4.0. However it introduced a significant problem with volume over Bluetooth. Any audio from the iPhone over Bluetooth is very low, to the point of being inaudible, even with volume turned to max on the Bluetooth device and the Bluetooth volume on maximum on the iPhone.
After much discussion over many threads at the Apple support boards, a number of 'fixes' were found but most of them resulted in temporary resolution. These includes resetting iPhone settings and/or deleting the Bluetooth device from the iPhone and re-adding it. This thread discusses the actual fix, and I have pasted the contents below.
This was tested on three different iPhones; doing it this way has corrected the constant disconnecting so you can now walk 30 feet or more away from your phone and the headsets have no muffled sounds that people on the other end were hearing. As a matter of fact the Bluetooth headsets sound the very best they ever had.
You can do this yourself; backup your phone to iTunes first. If you don't feel comfortable doing this your self call Apple support and ask them to walk you through this. [crarko adds: You can also read this, this, and other related Apple KB articles.]
Once you've completed a backup in iTunes go into Finder on your Mac and navigate to ~/Library/iTunes/iPhone Software Updates and you will see the latest software update that is on your iPhone. It has a file name ending in .ipsw. You'll have either 4.1 or if you have not updated you you will see 4.00, 4.01, or 4.02 whichever you have right click it and delete it.
Go to the summary page in iTunes and restore your phone. When you are done it will automatically detect and ask you to install iOS 4.1. Click OK and let it install.
You now have a totally clean install of 4.1 with no other conflicts from previous updates with corrupt Bluetooth issues. Now after the 4.1 installs iTunes will ask you if you if would like to restore from a previous backup or set up as a new phone. You must select new phone this is the most important thing to do!
Everything is backed up in iTunes and you will not loose anything. The only thing you will have to do on your phone is personalize it the way you had it before. No big deal because now your Bluetooth set will be working perfect. Your music, apps, videos, books, photos will all be there for you; just check the items in iTunes that you want back in.
The whole process should take about an hour, or perhaps longer if you have a large music or video collection to sync. Trust me if you do it this way it will work. Feel free to call Apple support and tell them you want to do a clean install of 4.1 and you want it set up as a new phone. Tell Apple you want to remove the previous software first.
[crarko adds: I haven't tested this one since I don't use Bluetooth headsets. I've edited out some of the lengthy verbiage of the original post and made some grammatical corrections; if you want to read the original in full the link to the thread in Apple discussions is provided above. The basic idea is to do a clean install of iOS 4.1 and not an upgrade, and then set up as a new device so the problem isn't reintroduced from a backup. I've had to do that before and it can take some time to sync a large library of media and apps, so make sure you have time allocated for this before beginning.]
Mac OS X Hints
http://hints.macworld.com/article.php?story=20100930054334183