Many of the already suggested sound like winners. Here are some others off the top of my head...
* Spice ("The Spice Trader", "Spice Trader's Cafe", "Spice Trader", as funky BoHo kind of themes, but for a more modern bistro/grill feel....just "Spice" might work, or "Spice Grill", "Spice Cafe", "Cafe Spice" etc.).
* Mata Hari (I'm thinking of an entire ambiance based on her...A mysterious, seductive, belly dancing, spice and tobacco filled aroma, bean bag chair, sitar music, hookah lounge kind of place)
* Aladdin ("Aladdin's Lair" maybe?)
* Taj Mahal (Associated with exotic, elegance.)
* Opium (Sounds like a nightclub in South Beach, but what the heck?)
For fun...
* The Curry House (Just because it'd be fun to ask a taxi for "el Curihau", lol)
* Gandhi's fight club (Aren't I funny?)
* Bali-Ho, Buddha Bistro
* Hookah'd it be now?
* Hookah'd ask for more?
* Hookah-Hookay Burning Love