I too don't have any ideas. I've tested my contacts navigation during this thread and they work just fine. The last thing I might ask before opening a support ticket, is to post a cropped screenshot of one address you're interested in from your Contacts so we can see the address entry, then a screenshot of how Waze shows that entry in the navigation search results.
Like so:

