Now that multi-step is officially no longer supported, I'd like to propose revamping the checkout logic to work better with single page. If customer selects a specific shipping method (say the default), but the methods change between that selection and processing of payments, the shipping hash fails and order is rejected. That made a lot of sense in multi-step, but has a detrimental effect in single page (order fails and customer may bail).
The only thing that should really matter is if the type or cost of customer's chosen method of payment has changed. For example, if I select the cheapest default rate and, after submission, the cart determines 2 other methods are also available, it really shouldn't matter... order should be processed. The exception would be if, for example, customer selects expedited and it turns out not to be available.
I understand in multi-step, a shipping hash change at the payment step likely meant that something changed about the underlying cart configuration. In single page, the culprit is more likely that shipping options didn't update after customer updated an address field.