I posted a petition write up for this, but I feel that it may need to be looked into as a possible quest bug.
Upon handing in my sealed letter to Brother Hayle, after I had collected all the quest pieces, I received the note which I opened and verified that it was the same note that I found on this guide here.
http://www.bonzz.com/soulfire.htm
Following this guide as well as a couple others, I did reference Wiki and Allakhazam. But I found some older guides that seemed to be more detailed as this was the first time I had actually attempted this quest. I was almost certain that my faction was adequate with Brother Hayle, granted it my downfall was that it was not max Ally, but I had done quite a bit of previous Priests of Life faction work before heading down to him. Including, Bandit Sashes, bone chips, rabid pelts, Moonstones, bone chips, and GPs to Lashun or w/e his name is in Qeynos.
I think that the issue currently is that the faction requirements, at least on Red, may be set higher than what was originally intended in Classic.
Long story short, I turned in the sealed letter to Brother Hayle, receieved the note back from him that read exactly as the guide states, and I assumed that at this point my faction was sufficient, however it was not maxed Ally, which I should have just went ahead and done but oh well.
If a dev. could possibly take a look at this as well as my more extensive explanation of what exactly occured, I have it posted in the petition forum as well.