Yesterday, while playing as Saphery, I tried to pass one of the gates (I think it was the Unicorn-gate of Ellyrion) with my Purge-army. When I noticed that it wasn't possible, I negotiated with Ellyrion for military access (who were already my allies). That didn't help though.
Is there any way to cross the gates of one of your allies? Otherwise I would have to march my army all the way down the mountain chain and back up again to get to Nagarythe