MapRouteFinder.GetDrivingRouteAsync and MapService

I have a Windows Phone 8.1 XAML app that uses the MapControl to display maps. In the MapControls Loaded event, I set a valid Bing API key

void MyMap_Loaded(object sender, RoutedEventArgs e)
{
    MyMap.MapServiceToken = the key
    MapService.ServiceToken = the key
}

I know the Bing API key is valid because the watermark in the MapControl is not shown.

From the page with the MapControl I navigate to another Page where in the ViewModel I try to find a driving route:

var driving = await MapRouteFinder.GetDrivingRouteAsync(new Geopoint(new BasicGeoposition
{
    Latitude = Latitude,
    Longitude = Longitude
}), Detail.GeneralInfo.GpsCoordinates.Position, MapRouteOptimization.Time);

The problem is that driving.Status is always InvaldiCredentials.

Is there something that I am missing?

The documentation says

Note that you have to provide the authentication token in two separate properties in an app that uses both Map services and the Map control.

and I did this.

The Bing API key I use is generated for Basic / Public Windows Phone App. I also tried to generate one for Basic / Public Windows App, no change.

I have a working app that uses this token. I only set it to a Map control in XAML, and then I can use both the Map and the MapService, apparently.

My Maps key token is 22 characters long. The only way to get it is, AFAIK

Make an app
Upload it to the store but do not submit
You app gets associated with a store ID and you will see a map token
THAT is the token you will need

See screenshot. Is that the procedure you followed?

Also, make sure xmlns:Maps="using:Windows.UI.Xaml.Controls.Maps", not the old Bing control. Don't even know if the old control is still available in the Universal Apps btw