I had a lot of trouble with this too. Yes, you have to be in Ul'dah, and you have to enter from the street. In the normal menu when you approach the Wards, a new special location will be available called "Waking Sands". This location will only be available when you have these quests open. Aside from talking the NPC directly inside your instance, you will also need to go to the back of the hall as well. Good luck