I completed the come fly with me quest a while back and just now noticed the achievement did not unlock. What gives?

No idea. I've had a few problems with achievements. I haven't got the one associated with completing Ring-a-Ding-Ding. =/

if you used the console (~ key commands) at all on that character it sets it where you get no achievements.