Are you sure the phone isn't muted. I just went to mine and if you have the ringer off or on vibrate, then the GPS software will be muted. You can either hit the menu key and unmute or use the volume keys on the side of the phone.
I'm not positive, but I think the spoken navigation is using "text-to-speech" on the phone. It sounds weird like text to speech when it talks through my earpiece while driving with navigation active.
I installed it when I first got the phone before trying navigation, so that's why I'm not sure. It isn't an app from the market, but is something you need to download and install. Settings -- Text-to-Speech -- Install voice data.
