I have played with the State & Country picklist value UI for adding them, and it works OK for small amounts, but it is not meant for batches. I have 760 additional states I need to add for various countries, and the UI takes about 30 seconds per state you add. I've been trying to edit the Address.settings XML file that you can pull down via Eclipse, and am finding that while I can edit new (custom) states I've manually added via the UI, I cannot add new states for whatever reason.
Each time it complains about the ISO Code, which to be fair probably aren't real ISO codes, but it is what the client wants to match their existing system. (Values are 1-2 digit numbers or 1-3 character letters).
Invalid iso code B for state Burgenland in country Austria
As I mentioned, if I added this to the UI and went in to change one of the associated pieces of metadata (say the tag), it works fine.
Here is an example of what I tried, based on how the states come back if you look at custom ones you add in the UI and how they show up in the XML.
<countries>
<active>true</active>
<integrationValue>Austria</integrationValue>
<isoCode>AT</isoCode>
<label>Austria</label>
<orgDefault>false</orgDefault>
<standard>true</standard>
<states>
<active>true</active>
<integrationValue>Burgenland</integrationValue>
<isoCode>B</isoCode>
<label>Burgenland</label>
<standard>false</standard>
<visible>true</visible>
</states>
<visible>true</visible>
</countries>
UPDATE: Looks like I overlooked the note in the API docs about the Metadata API not supporting creates/deletes yet. http://www.salesforce.com/us/developer/docs/api_meta/Content/meta_addresssettings.htm