Hi,
When you get an error message regarding the shipping methods, it means that no shipping methods was found. Now if you have several shipping methods configured, it can mean that one shipping method was discarded for one reaosn while another one was discarded for another reason. In order to not confuse the user too much, only one error message is displayed.
So if you have several shipping methods configured, you might actually see the error message coming from the restrictions of another shipping method than the one you're looking at.
To know of the reason why a shipping method doesn't display for a cart, the best is to temporarily disable the other shipping methods so that you're sure you're getting the error message for that shipping method.
So please check on that.