Hi everyone.
I have problems with a bunch of these issues too. Some of which I have managed to solve, some that are still persistent.
I am working on a local copy, so the live site is still running.
It started with an upgrade from a pretty old version (1.6.0.6) to 1.6.1.23. Most of the problems have to do with how customer adds an address.
First problem was that ZIP code did not show, but was required. I solved this by changing some code in address.tpl in the theme. The the issue is still with the states that is required and but the list is empty. I have tried to update/change and do all sorts of things with the statesMangement.js file but nothing changes. Empties chase after each change of course.
Another bug I have is that when I change country the form does not auto update as it did before to represent the current country's form. So if I change from a country like Canada or US to a country that does not have states, the state field is still present. But it correctly applies postcode format rules and it's ok to make an address without state in this case.
I will continue looking for solutions but am happy if anyone have some input on this.
EDIT: Btw, I believe the issue is related to the theme itself, so even if it is an old bug it is not directly in the version 1.6.1.23, but it has something to do when updating to newer version that screws up theme-based implementations.