I don't think you can have a blanket solution to this. Different provinces have different issues. Quebec's different from the rest of Canada on this. However, I think Quebec has proven to do quite well, actually, with their French-language program just because we have a structure in which they're incentivized to learn French by getting a stipend every week.
I think one of the problems you're facing here is the balance between getting a job or going to learn a language. They try to balance both and sometimes have to pick one or the other. When they're put into these labour jobs for which they don't need to meet a high qualification or a certain language requirement, they might put it off. Then again, here you've having to balance two different issues.
If you want to create a service, and if you're putting language as a priority, you should incentivize them. Maybe it's a stepping stone to a job, some sort of stipend per week, which is how Quebec does it.