Each zone has a 2 and a 3 letters code. If you delete and recreate a zone without setting these, HikaShop won't be able to send them to UPS and you will have that error.
You should make sure that all the zones you added under the menu System->Zones have the correct 2 and 3 letter codes.