I don't have a Braintree account let alone a site set up with the module.

But, it would be helpful to know exactly how to recreate your exact situation on a new store:
- how to create the zone configuration affecting these transactions
- an actual billing address that would trigger the problem

Perhaps there's a combination in there that will expose a solution. Often zone-mismatches are a result of unexpected assumptions.