I'm running version 1.6 and everything has been set to GBP, location United Kingdom. It doesn't seem to matter which shipping method I pick I keep getting the above message during checkout.
I've made sure the product has a weight and dimensions. I've tried using fixed price shipping / free shipping / Shipping By Order Total / Shipping By Order Weight Shipping Origin Country = United Kingdom Shipping Origin State / Province = Leicestershire Shipping Origin Zip / Postal code = "My postcode"
I had got the meaning of "restriction" the wrong way around. I'd unticked all country's apart from UK, thinking that would only allow the UK that particular shipping method. It actually works in the opposite way.
...or if you are like us (booksellers) everything is measured in ounces but we sell semi loads of books. Max default is 1M ounces for shipping by weight calculations. That is only 62.5k lbs. Bump it up to 10M ounces and problem is fixed. (nopCommerce 3.5)