I've got the same problem. I could listen to voicemail with my headset on my old iPhone, but I have not been able to since I upgraded to 3G. I am using a Cardo Scala 600 headset, which is the same one I used on the old iPhone.
If some of you can hear you voicemail over bluetooth, can you also make voice recordings with you headsets using recording apps? I have not been able to do this, either.