There is something more to the faction required for this quest. One of my characters has no problems starting this, she has *every* piece of TDS group progression done, and her faction is apprehensive, and the harried page and vendors in Lceanium happily give her the quest and everything is great.
My other character cons dubious, and although he can get the quest from the concerned citizen, and the Scribe says of course he's a hero of the Combine, the harried page won't speak to him at all and he's stuck. His TDS group progression is very close to complete, but he's missing the last 2 missions All Rivers Lead to the Sea and The Cost of Balance. I'm still figuring out how to get his faction up to a place where he can start. I'm hoping he can complete the Disappearing Dragons but haven't got to the harried page step in that quest, and he might get stuck there too.
At any rate, I'm pretty sure there's more to the faction requirement than "need to have a small part of TDS progression done". I'll post more when I find a solution.