I have 3.5.1 on an iPhone 4 with iOS 6.0.1. I use T-Mobile with no data plan.
I have wifi at work and home, and start navigation using that. When I get to the other end, though, Waze almost never recognizes the wifi, so I can't submit anything. I have "Searching network..." in red at the top of the app, even though I'm on wifi, can check email, etc.
One suggestion I have for favorites is to fill the text field on the "Name favorite" screen with the name of the place, if it has one. If I've searched for "Smith's Olde Bar" and found it, it seems silly to have to retype the name that's right below it.
Thanks for a very useful app!