Re: legally entitled to work in Canada;
Generally speaking this means that you must have a work permit that can allow you to work for any company in Canada (not company specific) or be a permenant resident. This company will not want to go through the LMO & WP process for you.
If you have an open work Visa, I am sure this will not preclude you from applying