I have a similar problem, but the above solution doesn't do the trick.
Even though logging in I still get the same problem, the volume is too big for any shipping method.
It seems to only pertain to one product though, I just cannot see what the difference is between the different products. The only difference is that there is a free download attached to it what i can tell, but that shouldn't affect anything, should it? My main tax zone is Sweden.
Here are some screenshots
Charachteristics of the first product that is working
Charachteristics of the second product that is working
Charachteristics of the product that is not working
Shipping methods