[wtbob]

I don't get at all that it's a genie — it looks like a boy with a weird matte blue squashed halo.

I don't think there's anything wrong with the idea of a genie (although note that AFAIK Sikhs & Turks have worn turbans, not Arabs), but the logo as it is just doesn't look like one.

Given the small size of the screenshots, maybe it'd be a good idea to consider a more abstract or line-drawn logo?

[agr_abhi]

An abstract logo is usually less memorable (unless you become well known). Genie was used as it resembles human and also signifies the app can do lot of magic for you.

As you mentioned, due to size we can't show entire genie there. So might have to either just keep the name and show genie separately in full or think of some separate image in logo