That’s because the quest to go there actually starts in Ashenvale. I think it’s at the Silverwing Refuge Camp or somethin like that.
You talk to the NPC to get a quest to go to Stonetalon via carriage and they drop you off and then you can start questing.
(Source: Done Stonetalon many many times on retail, which is what Cata Stonetalon is at this point)