I did this on Elite a couple nights ago and didnt notice any Red Named efreeties at all.... Not sure how I could of missed em.... The Air Eles were a PITA because our Sorc had burned through all his mana by the time we got to em somehow..... but overall, we barely noticed the difference.
I'm not sure why the quest had to be changed, but I dont see this as a reason to cross it off any lists. I guess the 2 shortcuts were not intended. I never used the Shortcuts when I solo'd on my clerics anyway.. Crappy Jump...