By the way, I had the same issue with one of my clients and the problem was that the shipping module was selected to a certain region while the checkout was done for a user outside of that region.

The problem is that there is no indication what might cause the issue but only the fact that you get redirected back to the beginning of the checkout process.

I hope that makes sense...