Somewhere, a linguistics major is angrily screaming at his monitor that 'genie' and 'djinni' are derived from the same Arabic word, and that making one a subset of the other is therefore ridiculous. Wherever you are, know I understand your frustration.
Djinn have seven outsider HD; in exchange they get a heap of bonuses. Ability boosts range from +8 to +4, the (perfect) fly speed is pretty good, and being Large won't hurt most builds either. Improved Initiative is something everyone can use. Immunity to acid has been randomly added in for reasons unknown (I guess being air and flesh makes you more acid-resistant than either of those on its own). Finally, there's 100 feet of telepathy, also known as 'no-selling all stealth since 2005'.
The genies also have a couple of abilities directly stolen from air elementals. Air Mastery is just an annoying bonus to keep track of, and Whirlwind isn't that great without a non-melee attack standard action to use while you're using it. Find some class feature that works with it or convince your DM whirlwinds can still wield bows.
Hidden away in a dark corner of the statblock is Plane Shift, an at-will version of the similarly-named spell that conveniently also affects allies. Not bad!
Finally, djinn have a number of SLA's. Invisibility is good for, well, turning invisible (though don't be surprised if a foe dispels or detects it), and at least it's at-will. Create Food and Water is nearly useless (so your party is mid-level, but without a survivalist, divine caster or everlasting rations?), and Create Wine has little middle ground between 'nice piece of fluff' and 'breaking the economy '.
Speaking about breaking economies, there's Major-Creation-with-permanent-vegetable-matter, able to create over 86 million GP per use. It's also got uses for creating nice food or short-lived adamantine weaponry, but who needs those if you can buy a small kingdom per day?
The further SLA's have their uses. Persistent Image is better than anything the illusionist has access to at this point in time, Wind Walk further reinforces a djinni's role as the party cab, and Gaseous Form has some use too.
In the end, I'd say +2 LA is warranted here, following the outsider rule of thumb. Djinn have some very powerful abilities and while they're not as smashy as similarly-leveled outsiders, they should be able to fit in just fine.
Three extra RHD in exchange for... what amounts to at-will Wish. Sure, there's some debatable text (if you 'perform no other services', can you still fight along the party?), but in practice this means a simple familiar or helpful party member can let you alter reality thrice per turn.
Obviously, this is going to get asterisk-ed. With their Wishes removed, noble djinn are basically just regular djinn that get more HD. That said, regular ones have +2 LA anyway, so I think reducing it to +0 is fine.