I am trying to call the webservice and getting the following error:

System.CalloutException: Web service callout failed: WebService returned a SOAP Fault: <E97007> The supplied Zip+4 code of '87144' is invalid. faultcode=a:ApplicationException faultactor=

I get this error from a class generated from a WSDL in a sandbox org but using a dev org with the same WSDL I get a little more detailed info. 

06:50:06.284 (284395000)|CALLOUT_REQUEST|[197]|
<?xml version="1.0" encoding="UTF-8"?>
	<env:Envelope xmlns:env="http://schemas.xmlsoap.org/soap/envelope/" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
		<env:Header />
		<env:Body>
			<GetAccountDetailsByAccountNumber xmlns="http://tempuri.org/">
				<AccountDetails>
					<AccountNumber xmlns="http://schemas.datacontract.org/2004/07/xxx.xxx.SFDC.Contracts">
						010655421
					</AccountNumber>
				</AccountDetails>
			</GetAccountDetailsByAccountNumber>		
		</env:Body>
	</env:Envelope>

06:50:06.284 (284490000)|CALLOUT_REQUEST|[197]|
GetAccountDetailsByAccountNumber_element:[AccountDetails=GetAccountDetailsByAccountNumberRequest:[AccountNumber=010655421, AccountNumber_type_info=(AccountNumber, http://www.w3.org/2001/XMLSchema, string, 1, 1, true), apex_schema_type_info=(http://schemas.datacontract.org/2004/07/xxx.xxx.SFDC.Contracts, true, false), field_order_type_info=(AccountNumber)], AccountDetails_type_info=(AccountDetails, http://schemas.datacontract.org/2004/07/xxx.xxx.SFDC.Contracts, GetAccountDetailsByAccountNumberRequest, 0, 1, true), apex_schema_type_info=(http://tempuri.org/, true, false), field_order_type_info=(AccountDetails)]::SFDC_STACK_DEPTH=1 SOAPAction="http://tempuri.org/IAccountDetails/GetAccountDetailsByAccountNumber" User-Agent=SFDC-Callout/28.0 Accept=text/xml Content-Type=text/xml; charset=UTF-8 

06:50:07.626 (1626529000)|CALLOUT_RESPONSE|[197]|
<s:Envelope xmlns:s="http://schemas.xmlsoap.org/soap/envelope/">
	<s:Body>
		<s:Fault>
			<faultcode xmlns:a="http://tresoap.intecbilling.com/fault/2.0">
				a:ApplicationException
			</faultcode>
			<faultstring xml:lang="en-US">
				&lt;E97007&gt; The supplied Zip+4 code of '87144' is invalid.
			</faultstring>
			<detail xmlns:soapenv="http://www.w3.org/2003/05/soap-envelope">
				<trefault:Detail xmlns:trefault="http://tresoap.intecbilling.com/fault/2.0">
					<trefault:Message>
						&lt;E97007&gt; The supplied Zip+4 code of '87144' is invalid.
					</trefault:Message>
					<trefault:ErrorId>
						97007
					</trefault:ErrorId>
				</trefault:Detail>
			</detail>
		</s:Fault>
	</s:Body>
</s:Envelope>

I don't exactly understand what is happening here.  I have 12 account numbers to test with, but only get this error with 3 of them.