Google Maps No Route Found on Android device

When using Google maps for navigation in an Android application, the directions are shown in the emulator but when running on the device (signed APK as well), the following message is displayed.

What could be the reason and how can this be resolved?

Solution

From what we came up with in comments, it probably is due to policy changes using google maps API. In production ready, signed apk, restricted API key should be used. Also, to get some free API requests a billing details must be set. More info and transition at https://developers.google.com/maps/documentation/android-sdk/signup