The company is trying to do something clearly spelled out as "not allowed" by (I expect) every labour standard jurisdiction in Canada. They're opening themselves up to a huge liability by doing so. Not just for an apology and a "sorry, my bad" letter, but punitive damages (because it's a flagrant offense). It would be worth taking the time to discuss with a lawyer before rolling over. And often, legal costs are covered by the employer, to prevent big corporations from bullying employees who don't have the resources to otherwise fight. So the company would be paying to sue itself. And as long as the OP has a strong enough case, a lawyer would do it on contingency, so the OP would have nothing to lose.
But as far as that goes... Canada has "at will" employment. An employer can turn around and fire someone without cause, as long as they give the proper notice and severance. So I don't know what's to stop them from parking the new contractor somewhere for a short period of time (or suggesting holidays), bringing the mat leave employee back, firing them after a month, and then re-instituting the contract employee. Trying to prove a wrongful dismissal in that case would rely on a judge's discretion, which would be a crap shoot. If the OP was brought back for a day, no question. A month? Fuzzy. 6 months? Fuzzier...
Of course, now that the company has given the OP notice, they would likely lose any reasonable doubt on a termination action...
C