There are a lot more damage dealers than healers or tanks, so it can take a long time to find a full group if you are using the Duty Finder. But don't re-roll if you don't want to, instead find a Free Company or Link Shell with people who can queue up with you.

I have done this on a few of my characters and it is much faster. If I ask in LS for people to help me with a story locked dungeon, I can usually get at least a partial group in under 20 minutes. And so long as I queue up with a tank, I usually am able to get in instantly from there. If I do it with the DF, as you have seen, it can take hours.