I'm sure you've figured it out by now, but in case y'haven't, Deep Dungeon is only accessible after clearing (SPOILER)Murond Holy Place but before going to the final set of battles at (SPOILER)Orbonne Monastery.