Quick reply...
Not sure if it's the issue, Evok, but routing is (at least, now) only possible if Internet (more precisely, Google routing) is available. As far as I know, absence of Internet will not cancel the routing, so when Internet is turned on, the route is found (even if it is several hours later? as long as you haven't cancelled it by then).
If the behaviour ("geocoding..." instead of routing) persists when Internet is available, see if there are any errors logged. (Shrugging - I don't use routing (especially online routing) much (if at all), so I can only hope my advice helps).