This has been driving me crazy. I know I read this book/books (possibly a trilogy) around the same time as reading Sabriel etc and the Windsinger trilogy. I don't remember a lot but I think it was about an immortal man (Sure that his name started with A) who had bright blue or purple hair (I remember a line about how hair constantly changes colour but only a few people live long enough to see it go past grey). I think he recruits young people and sends them places to do missions (can't remember if its time travel or different universes etc) It ends with one of the girls falling in love with the immortal man and deciding to stay with him. I know that this isn't a lot to go on but if anybody knows what this is, I will be very thankful. Oh and I think one of the books was called Key to the Door or something similar?
The series is called "Guardians of Time" by Marianne Curley and the books are "The Named", "The Dark" and "The Key".
The characters you're remembering are Isabelle (the girl) and Arkarian (he isn't truly immortal but it is correct that he doesn't age and his hair changes colour over time).