Make sure civicrm_country and civicrm_state_province is synced with ISO 3166

Go to http://www.iso.org/iso/country_codes/updates_on_iso_3166.htm and check whether there were any updates on ISO 3166-1 published after V-12.

Also, try to either obtain an electronic copy of ISO 3166-2 and use that to (re)build full state_province table, or extract that information from Wikipedia (which seems to have it, but is less trustworthy a source on this).