I have a storm and I am using a Jawbone and it is on T-mobile and I am not having any issue with it did you make sure in the preferences that you have the voice set to high?
It works with my Storm ... LG-960 headset, upgrade your version of VZ Navigator to 4.2.21.40 ... I still find the speaker in the phone is louder and easier to hear though even with my headset cranked all the way up. I hear better through one ear though and use the LG in my "bad" ear because I don't like plugging the "good one" up when I'm driving ... phone calls are noticeably higher volume through the LG than Navigator's voice is ... I even experimented with the different "voice choices".