I got this yesterday too, looking for answers I came across your thread.

I had one order go through without issue, and another failed that was going to a USMC APO address.

I assumed it was due to the APO address being "seen" as invalid or not matching the Paypal address for the customer.

Either that or they changed the "Ship to" address manually to the APO and it didn't like that.

So perhaps your issue is similar to mine in that the cart doesn't like it when they change the ship to address(?), or if the address is determined to be invalid for some reason.