This reminds me of the time when i was a newbe and coudn't get through Shard's of Orr to get to Gadd's lager. So I spended bout 2 hours finding a way from lion's arch to that place. But although prophecy's (and Ascalon) and Eye of the North are on the same map and continent, the zone's are totally separate, only allowing maptravel to already unlocked outposts and towns.
To add to Marty's aswer. Keep in mind that if your from nightfall and follow the normal questline you'll get to Eye of the North significant earlier then that you get access to Lion's arch. This can be bypassed by getting a taxi or ferry (first to the docks and then from there to lion's arch). Last time I checked it was hard to get the later.