I just got my Rezound about 3 weeks ago and I tried Navigator and there was no voice, even though the option for a voice was clicked on, I tried clicking it on and off and still no voice. And yes, the volume was up!
Can you play music through the external speaker? If you can then that verifies that the media volume is up and thus nav-voice should be audible as well. Have you restarted the phone by pulling the battery out completely and then replacing it? If not, try that and try navigation again.