Basically google doesn't have data for all countries/regions and on some Australian network (should be noted somewhere in the first pages of this thread) the operator was doing some nasty caching that delayed the delivery of the data and the app just said no route found because the answer wasn't fast enough or somehow modified.
Try it with wifi and see if this work (not the navigation itself, just getting the routing infos).
Another thing that you can try is to see if maps.google.com can generate directions for the two locations that you want to route (from a normal browser, maybe best on pc)
dear i am using it currently through wifi , and maps .google.com can generate the routing between two points in dubai i have tested that thing on my lap top but i need it on my mobile which i cannot...! one more thing buzz sattelite and other layers are working fine , except for traffic layer...
i think i am the only one in UAE who wants routing in google maps....! feeling so lonely ....!