Because Postie uses caching for data from providers, this data can potentially cause issues by referring to old, outdated data. In this case, clear Craft's caches by going to _Settings → Clear Caches.
Postie sends the total dimensions of every single line item in the cart to the provider APIs to calculate the total shipping costs based on the dimensions. Make sure you have set up dimensions for every product.
Also check you are using the right Weight Unit and Dimension Unit in Commerce → Settings.
This can happen when trying to request too many provider services in one go, often on a server with limited hardware resources. We'd recommend to ensure PHP 7 is installed, the server as adequate resources and memory limits. Decreasing the number of providers to fetch will also speed this process up, so ensure you enable only the services you require.
Fortunately, Postie logs all errors and API responses to a log file under
craft/storage/logs/postie.log. If you're having issues, see if there is anything in this log file that points to the issue, or get in contact.
Available for Craft 2 for $49, trial locally for as long as you need.