It wasn't madrasas per se - but all religious-based schools - be it a Pentecostal school or a Jewish day school, or yes, a madrasa - provided they are approved and teach the standard Ontario curriculum (which limits how nutty these private schools can be).
It was a terrible policy, and I don't think it's all that liberal - it promotes private education at the expense of a pretty good, universal public education system here in Ontario, and was more to pander to Protestant but not so much the old-line, more liberal Christian groups such as the Anglican and United Churches) and Fundamentalist Christian and Jewish groups. It might have starved public schools once the cost of all those tax breaks were clear. The right policy would be to abolish the Catholic system - that would have been the liberal and risky thing to do.