How have you selected "Quebec" for addresses?
Are your tests using QC or PQ for the province?
What do you have inside the Admin->Locations/Taxes->Zones Definitions->Quebec->DETAILS area?