Invalid Shipping address provided to PayPal

Here is my issue, I am using the USPS live checkout service and PayPal standard as my payment gateway with eCart. On some orders I am receiving a message that reads:

"Unable to process payment. Please contact the mercahnt as the shipping address provided by the merchant is invalid, and the merchant has requested that your order must be shipped to that address."

I have contacted PayPal and according to them my settings are set to allow to ship to what address the customer has provided. I have also worked with them to figure out this error seems to only appear on domestic orders when the full state is spelled out and not when the 2 digit abbreviation is used. I use a text field because I also ship to international addresses and to the best of my recollection it has only been on domestic orders that this problem has occured.

I also contacted the USPS tech support and they said they have not heard of such an issue before. So I am looking to see if any one here has run across this problem or has any suggestions to help possibly clear this issue up. Don't like losing sales.

Thanks in advance