Thing to work with:
Genies and Gents (is that the proper plural of Genie?)
Magic Carpet Ride
Magic and Minarets
Time In A Bottle
Midnight at the Oasis
Other things I think of: Sultans, camels, tents, dates (the dried fruit, not romance), harem girls, eunuchs (let's be fair, they go with the harem girls) and 40 thieves.
An aside thought:
Since the story is about a woman who saves her life by telling her husband/master 1001 stories, maybe everyone in the class can contribute a story/memory about their time at school and you can self-publish a small book and give each student a copy. Ask the art students to do some illustrations.