New Inn Quests not Flagging

[Melinia]

20, I think?

Correct. You need to be level 20 to do "Mysteries of the Red Moon". That's pretty easy to get, though.

Once you're level 20, go talk to the Lalafell outside the Inn Rooms in Uldah, and you'll get the quest.