A number of address-handling improvements were made in Zen Cart v1.3.9
Upgrading may resolve the problem for you.