FYI - I had same issue with UPS, I found if I change the UPS setting to ALL Locations - it works, is set to only US, I get only the store location state.
Additionally, since I only have enabled US for this install, all the countries (even though turned off ) show in the country dropdown, but if one is selected that doesn't have zones enabled it shows NONE
Just hadn't posted this yet.
Lee
PS abolabo - I think they do an IP check - if you want me to get you a test account let me know.