Someone else had this issue a week ago, I linked him the wowhead article and he found the solution, though he didn’t say what it was.
Take a look in that thread, look at the wowhead article and see if you can find the missing bit 
Edit: I believe the other player did not realize he needed to go to the Stormwind Embassy to get the quest to unlock the race.