I have noticed the same thing. It will not find any contacts that has only a company name and no first or last name and that search worked in the Previous Version. Also any search brings up a lot of contacts that have nothing related to the search word. Now when it can't find the contact address I am looking for, i just copy the address from the Contact and Paste it in the Navigate Search Field until this issue is resolved. I have also deleted the Waze App and reinstalled it again. Please get this issue Resolved ASAP.
iPhone 5, IOS 6.0.2
Waze Ver. 126.96.36.199
Points: 187541 US Ranking: 1714