Posting on behalf of my friend.
He has leveled a character to 80 through questing in Isle of Dorn as well as doing some dungeons, then decided he wants to go on his Paladin or Evoker. The Evoker/Paladin have done the pre-quests and have arrived in Dornogal, however his character is ineligible to queue for war within dungeons.
496 ilvl, level 70, has done the intro quests, already has a level 80, a role has been selected etc.
We are baffled and confused as we want to queue and dungeon together, both are the same faction
:Edit: by questing until level 71, the dungeons unlocked. Very weird