I'm not persuaded that the flange alone is responsible for your leak. However, I will let others more knowledgeable weigh in on that.
What you saw under the toilet was a "base" of plaster of paris which many old-timey New York plumbers use to "set" a toilet. It's an ancient art that some still practice -- and those that do will massively condescend to those of us homeowners who have installed an ever-enlarging number of toilets ourselves without the "base" in which to "set" it. It's totally-unnecessary, because shimming the toilet if the floor isn't level is all you need to do, and no manufacturer recommends that you do a plaster of paris base. It seems to be a very local practice; a thread I wrote earlier this year turned up almost nobody outside the NY tri-state area that had ever even seen it.