Zones won't update when changing countries.

It is because of this code, right?

  $items['uc_js_util/%'] = array(
    'title' => 'JS utilities',
    'page callback' => 'uc_store_js_util',
    'page arguments' => array(1),
    'access arguments' => array('access content'),
    'type' => MENU_CALLBACK,
  );

Ubercart Addresses makes use of the API Ubercart provides, so I think you should file this issue in the Ubercart issue queue if you want a different permission for the zone updating.

Another possible solution is to write a custom module and implement a hook_menu_alter() and a hook_perm() in it:

<?php
/**
 * Implementation of hook_menu_alter().
 *
 * Change the access setting for Ubercart javascripts callbacks.
 * (e.g. zone updating)
 *
 * @param array $items
 * @return void
 */
function mymodule_menu_alter(&$items) {
  $items['uc_js_util/%']['access arguments'] = array('access zones');
}

/**
 * Implementation of hook_perm().
 *
 * @return array
 */
function mymodule_perm() {
  return array('access zones');
}
?>

The root of this problem lies with Ubercart, not Ubercart Addresses. It can be fixed with writing your own module (see #3) or by filing an issue in the Ubercart issue queue.

Issue closed.