Check internet settings on your phone... same happened to me - new phone with all apps connecting with no problem, except Waze.
Default APN (access point name) was set to wap instead of 3g. If you are unable to set this correctly, ask your carrier for help.
I posted then on forum viewtopic.php?p=238286#p238286
Several other related topics might be found too
if it looks strange, it's my phone's fault