INAStreetDirectionsAgent.Execute fails with ArcGIS 10.1

[ArnaudFradin]

I am working on an extension for ArcMap using the INAStreetDirectionsAgent class to generate the itinerary directions and display them. The example given in the documentation was followed step by step:
http://resources.arcgis.com/en/help/arcobjects-net/conceptualhelp/index.html#//000100000390000000

It worked perfectly with ArcGIS 10.0, and still does. On two computers, both Windows 7 64 bits with the same version of the extension, the only difference being ArcGIS 10.0 on the first and 10.1 on the second, the directions are only working on the first.

The error seen on the second is the following: "System.Runtime.InteropServices.COMException was unhandled Message=Exception from HRESULT".

Has anyone had a similar problem, or an idea of what could have changed between 10.0 and 10.1 ?