Are you getting a shipping quote returned on your confirm page? If so then the server behaviors are working correctly. Are you getting to the shipping failure page? Normally if you create the checkout with the wizard you will get to the shipping failure page if there is a problem with the shipping. If you are getting to the checkout failure page it indicates that there is a problem with the checkout that is occurring.
What is the gateway you are using for the checkout? There may be a problem with the transaction. If you post back with the details about the gateway you are using and the page you are getting to I will try to help you troubleshoot this further.