Hey there,
I'd also try adjusting the volume on the BT headset as well.
You might also try re-pairing the device. (delete it off the Treo & re-add.)
If all else fails, there's an app called VolumeCare or something like that. It will allow you to up the volume even further on your BT headset.
Get it here:
http://mytreo.net/downloads/details-685.html?VolumeCare