OK i got it!
I had to add some logic to the queries, as your setup would only work if they were from USA. So now I do a Country query first. If they are from USA, I run the query with the state/zone_code, if not, I run the old query since there would be no matching zone for a province (which is what the state field becomes if you are from another country).
I added the GetCountry function as a PHP function now, I had to make an array of all the countries, which is how I had to do the old javascript one anyway (i just copied the html source and split on the html code snippet delimiters :P)
I suppose I could add the GetState as a php function and save myself from having the logic on the queries, but I don't know that either way really matters more than the other. As long as it works, and it works good :)
I've got it working with all countries now, and I've rewritten a bit of the code. I'm going to look at adding APO address support if its easy enough and I hope to have a new version within the week.
Thanks again lnksys for your help and for all those who help test it and enjoy it.
:)