I have to agree with you suggestion that is may be the module ...

I have tried Zones on PayPal and Check/Money Order and they work fine when NOT using the Country with All Zone, but rather use the Country with each individual Zone ...