I can confirm that The Sand Charm (http://ffxi.allakhazam.com/db/quests.html?fquest=234) is required to flag this quest (The Gift).
I am a fisherman on a new character, and wanted access to Zaldon gutting my fish. Therefore I started this quest line, having done no other Selbina or Mhaura quests. I could not get The Gift, so I followed the advice below and went to Mhaura to do The Sand Charm. Upon completing it, The Gift and subsequently The Real Gift were accessible.