I have made addresses for Australia, Singapore and Iceland and have no problem on the checkout_shipping page ...

If you go to any of these Customer Accounts in your Zen Cart Admin and do an Edit and Update do you get any errors?