I did this, and then I like, restarted the campaign thinking something glitched. Apparently I wasn't really paying attention, I guess, to the dialog when I first went north from the second set of footprints and rescued some guy from the burned city. He told me I had to go back to the burned city and bring him a book, and I wasn't doing that. There really should be a different message besides the past the footprints message for those who followed the footprints, but still need to go back and bring him the book. As for the obsidian gate message, that was driving me crazy for awhile too.

*spoiler alert for op* Also, when I brought the guy the book I walked my troops all the way back to Tarth and boarded them aboard the ship ship she gave me. Then I sailed to the obsidian gate, without ever sending an overland army. When I got there, the dialog seems to have assumed I would hit the obsidian gate from the outside first, and then sent a ship around it. It spoke of reunions between my armies, when in fact they hadn't ever seperated.

There is a lot of room for improvement in some of the interim quest dialogs, no flags to detect certain actions on the player's part can lead to some confused text.