I had the same thing happen, using WooCommerce Services plugin with Canada Post rates. One day all the rates were calculating correctly in the cart, the next day they weren’t.
What I finally learned was that the shipping zone list is read and prioritized from top to bottom.
I had added a zone for free shipping in Canada that was appearing above the regular Canada shipping zone in the list. And my free shipping zone requires a coupon code.
So the free shipping option for Canada was not being met and the plugin was not seeing the regular shipping zone located below it in the zones list.
The solution was to drag and drop the free shipping zone below the regular shipping zone and all worked correctly again. I had no idea the list was prioritized this way.
So I’ve arranged my zones from broadest at the top to narrowest at the bottom, with anything that requires a coupon code at the very bottom of the list.
Hope this solves it for someone else!