I already completed the mission at Al Maajik and I have to complete Butterfly's requests to move on. I DO NOT want to walk all the way there, But I can't find Air Reveria. Where is it?
If you mean the Air Reveria branch in Castele, it's in the West Castele area. From your room (Pam's house), go west, past the shopping district. The next screen will be West Castele, and the airship dock is there. The icon on your lower map looks like some sort of blimp, and the person you want to talk to is one of the ones named/labeled "Staff".
I believe it costs 100 dosh per party member to fly to Al Maajik.
I know this is kinda old already, but for completeness sake, if the OP was meaning "where is the Air Reveria branch in Al Maajik", he should look at the northwestern part of Al Maajik Outskirts =)