I have a client based in Canada as well, and experienced the exact same issue. After a number of hours debugging the API calls, I finally found the solution.
The Solution: You must disable insurance.
I achieved this by configuring the insurance field to 1,000,000.
After making the change, shipping rates were restored for domestic Canadian shipments as well as United States shipments.Insurance
Insure packages when order total is greated than:
1000000
Bookmarks