UPDATE: There is now a known issue for this that you can track "Generate WSDL" generates a WSDL that does not contain the definition of the compound types address and location if API version is 30.0 or above
I tried adding it myself as a web reference. This is the message I got:
Custom tool error: Unable to import WebService/Schema.
Unable to import binding 'getLeadInfoBinding' from namespace 'http://soap.sforce.com/schemas/class/getLeadInfo'.
Unable to import operation 'getLeadAddressByEmail'.
The datatype 'http://soap.sforce.com/schemas/class/getLeadInfo:address' is missing.
Note that the last part here is important. It is telling you that there is no element named address defined in the tns namespace. The tns
namespace is set to "http://soap.sforce.com/schemas/class/getLeadInfo".
You will need to add a complex type for address.
<!-- Compound datatype: Address -->
<xsd:complexType name="address">
<xsd:complexContent>
<xsd:extension base="tns:location">
<xsd:sequence>
<xsd:element name="city" type="xsd:string" nillable="true" />
<xsd:element name="country" type="xsd:string" nillable="true" />
<xsd:element name="countryCode" type="xsd:string" nillable="true" />
<xsd:element name="postalCode" type="xsd:string" nillable="true" />
<xsd:element name="state" type="xsd:string" nillable="true" />
<xsd:element name="stateCode" type="xsd:string" nillable="true" />
<xsd:element name="street" type="xsd:string" nillable="true" />
</xsd:sequence>
</xsd:extension>
</xsd:complexContent>
</xsd:complexType>
<!-- Compound datatype: Location -->
<xsd:complexType name="location">
<xsd:sequence>
<xsd:element name="latitude" type="xsd:double" nillable="true" />
<xsd:element name="longitude" type="xsd:double" nillable="true" />
</xsd:sequence>
</xsd:complexType>
What release is the Org that you generated the Org on? It seems like a bug that they didn't include the required complex types for address and location.
I've raised this on the developer forum to see if will get picked up as a bug. Salesforce generated WSDL for Apex webservice missing address complex type