I just ran through Vaults of Madness on normal mode and the quest start marker did not appear at all. I hadn't done VoM on this toon previously. I had not entered that part of the map yet as had not completed the quest objective for Army of Meridia where you enter the chapel for the council of war, but I entered the dungeon as the group leader. Maybe the quest didn't appear for us because I hadn't "legitimately" entered that part of the map yet?
I asked in zone chat and another player said that they did not have any trouble starting the quest, but that it bugged out after the 2nd boss.