There may be a "fix" to ensure that an error message is properly displayed if the previously-selected choice is no longer valid ... I'm surprised you're not seeing any error/warning about that.

What template are you using?
What customizations have you made to the templates used for checkout pages?