Turn guidance to turns only (minimal), then go to the General Settings and see if you have a female voice selected. I'm guessing so.
When Waze doesn't think it has a street name loaded to say, it switches navigation instructions to the selection you have when in minimal mode. What's odd is that it is mixing them, so clearly it has the street information, but another part of some code thinks you don't and so switches the voice output info. That's odd.
Turn on debug mode by navigating to 2##2. Then, drive until this happens a few times. Then stop, go to Main->Settings->Help and Upload Logs. Then (re)post your issue, experience, and date/time you uploaded logs in the iOS v3.6 official feedback thread. (Navigate to 2##2 again to toggle debug mode off.)
(Later, I would recommend deleting Waze and reinstalling it. This shouldn't have to be done, though.)