Level 31 is more than good enough to go to the Flying Fortresses & to Ba'al too.
Once you go into the Hall of Echoes (or start Flames of Vengeance after that), you CAN'T go to the 5 Flying Fortresses in the Orobas Fjords and/or poisonous Broken Valley, never !
So be sure to do all the things you like to do before entering the Hall of Echoes (no way back !).
Flames of Vengeance is indeed an entirely different area, but I like that part very much ! Tons of Humour & Quests, lovely music tracks and it's fun to discover hidden things & locations, it's really an awesome part !!
I'm now L45 and I think almost at the end of FoV ...
I go (start) the foV part when my hero was level 34 .
(without using Wisdom or upgrading Mindreading skill)