I am on the lost story found part of the new story with one of my alts and I have cleared all three shrines. But Braham does not appear this time. All of my shrines have the green checks in my story log. Not sure what's going on.
Here's a solution another player found for this issue: https://en-forum.guildwars2.com/discussion/comment/1144279/#Comment_1144279