What page are you getting to when the shipping fails? Do you have the full request and full response bindings on this page for the shipping provider that you configured in the globals file?
Please post back with the shipping provider you are using and the exact error messages you are getting.