you have to do WinterTusk and get to I think nori brother then see your teacher for your phoenix pet then once you complete your phoenix pet quest then you can start your Efreet pet quest
Yeah, you need to do wintertusk and have completed the previous pet quest. I know it's tough and the level 78 aren't very good, but you need it to get the 98 pet, one you will not want to miss out on! Good luck!