Make sure the State code is a valid APO state address, such as AA, AE, or AP.
Having something like “Armed Forces” in the state area will cause this error.
Pulled from Wikipedia:
Three “state” codes have been assigned depending on the geographic location of the military mail recipient and also the carrier route used for sorting the mail. They are:
AE (ZIPs 09xxx) for Armed Forces Europe which includes Canada, Middle East, and Africa
AP (ZIPs 962xx – 966xx) for Armed Forces Pacific
AA (ZIPs 340xx) for Armed Forces (Central and South) Americas
Yuji Tomita 