I've noticed a bunch of issues logged and topics posing questions around being unable to fly certain routes even though the aircraft have available hours and the runways are long enough.
If you're in a non-Open world, you have to follow the political restrictions built into the game. AE has a page specifically on this - be sure to read it over!
The Open worlds, O1 and O2, ignore all of these and the restriction that all flights have to start or end in your home country.
Hope that helps!