Thanks all for the help. It gave me ideas to solve the problem in my Hyndai Elantra in a slightly different way.
You don't need to uncheck the Media Audio option under the phone's Bluetooth settings. Do that only if you want to hear the navigator through the phone's speaker (maybe because you still want to hear the CD playing through the car). But, if you want to listen the navigation through the car's speakers, this is how to do it in the Elantra:
As I said, leave both the Phone and Media audio checked. On the car's media panel, push the "Media" button (which allows to select CD player, Radio, USB, etc.) and choose the "RT" option (I had never done that before). A message on the car's display asks you to play your phone music, but it actually will play the phone navigator's voice too.