There could be a couple of things going on. You are probably experiencing a problem with either the shipping or the checkout. If you can see a shipping variable in the URL when you get the checkout failure page then it is a shipping problem. If you don't see this then it is probably a checkout issue. You will need to add in the request and response info for the part that is not working to see what the problem is.
If you see shipping=fail in the URL when you get to this page post back and let us know the shipping provider you are working with.
If you do not see this in the URL follow these steps to get the debug info to show:
showpost.php?p=34342&postcount=3