When you get this error do you see the shipping details on PayPal? It sounds like it is just complaining about the shipping values. Have you tried this with other shipping values?
I think you might also get this error if you have specified shipping address required for orders and not passed the proper values for the shipping.