Sorry, it seems that there are no available payment methods for your state

I’m seeing an error on checkout, when using Multi Currency with my payment gateway (WooCommerce Elavon Converge EU Gateway).

The currency is GBP, which is definitely compatible with the gateway, since it works fine with Multi Currency disabled. The full message is:

“Sorry, it seems that there are no available payment methods for your state. Please contact us if you require assistance or wish to make alternate arrangements.”

On what conditions is this message generated, and how can I diagnose the problem? Perhaps it’s a configuration error on my part.