Yes, you would. You'd have a very significant problem, in that when the federal criminal law powers envisioned it, it was a power that uniformly applied to the entire country.
I think you'd immediately get a challenge that this law is not in fact about criminal law, but it's about social morality issues. If it's not uniformly applied, it raises the issue of it not actually being a criminal law regulation, as granted by section 91.27 in the Constitution.
I think the court has been pretty clear that criminal law has to be uniformly applied across the country, and that's not to mention Americans coming up to Canada looking for safe havens. I don't think you'd want the rest of the country going up north looking for safe havens either.