I ran into the same issue and instead of commenting out the catalogProductAttributeRemove, I actually looked into what was missing and added the additional sections to my wsi.xml file. Thanks to Juanma R. for pointing me in the direction of the file that needed to be corrected.
I referenced the entries for catalogProductAttributeCreate as a reference point for what other sections might need to exist to fix this. I don't really know anything about WSDL, just tried looking for what could be missing.
After I changed the file I refreshed all caches in Magento and confirmed the new entries were showing up in the WSDL file at /index.php/api/v2_soap?wsdl=1. I then removed the web reference that was added to VS 2010 and went through the steps of adding the web reference again. This time after adding it I got no errors.
The version of Magento that I was patching is Magento Enterprise 1.12.0.2 but I expect it's applicable to other versions that show this same error with catalogProductAttributeRemove.
Here is a quick diff I ran of what I changed in the wsi.xml file:
*** Z:\mage-1-12-0-2.dev\htdocs\app\code\core\Mage\Catalog\etc\wsi - Copy.xml backup Tue Jul 3 12:08:31 2012 UTC
--- Z:\mage-1-12-0-2.dev\htdocs\app\code\core\Mage\Catalog\etc\wsi.xml Fri Nov 9 18:40:58 2012 UTC
***************
*** 1509,1520 ****
<xsd:complexType>
<xsd:sequence>
<xsd:element minOccurs="1" maxOccurs="1" name="result" type="xsd:string" />
</xsd:sequence>
</xsd:complexType>
</xsd:element>
</xsd:schema>
</wsdl:types>
<wsdl:message name="catalogProductCurrentStoreRequest">
<wsdl:part name="parameters" element="typens:catalogProductCurrentStoreRequestParam" />
</wsdl:message>
<wsdl:message name="catalogProductCurrentStoreResponse">
--- 1509,1540 ----
<xsd:complexType>
<xsd:sequence>
<xsd:element minOccurs="1" maxOccurs="1" name="result" type="xsd:string" />
</xsd:sequence>
</xsd:complexType>
</xsd:element>
+
+
+ <!-- Added by Matt Johnson 2012-11-09 to fix VS 2010 support of SOAP reference -->
+ <xsd:element name="catalogProductAttributeRemoveRequestParam">
+ <xsd:complexType>
+ <xsd:sequence>
+ <xsd:element minOccurs="1" maxOccurs="1" name="sessionId" type="xsd:string" />
+ <xsd:element minOccurs="1" maxOccurs="1" name="attribute" type="xsd:string" />
+ </xsd:sequence>
+ </xsd:complexType>
+ </xsd:element>
+ <xsd:element name="catalogProductAttributeRemoveResponseParam">
+ <xsd:complexType>
+ <xsd:sequence>
+ <xsd:element minOccurs="1" maxOccurs="1" name="result" type="xsd:boolean" />
+ </xsd:sequence>
+ </xsd:complexType>
+ </xsd:element>
+
+
</xsd:schema>
</wsdl:types>
<wsdl:message name="catalogProductCurrentStoreRequest">
<wsdl:part name="parameters" element="typens:catalogProductCurrentStoreRequestParam" />
</wsdl:message>
<wsdl:message name="catalogProductCurrentStoreResponse">
***************
*** 1883,1894 ****
<wsdl:message name="catalogProductAttributeCreateRequest">
<wsdl:part name="parameters" element="typens:catalogProductAttributeCreateRequestParam" />
</wsdl:message>
<wsdl:message name="catalogProductAttributeCreateResponse">
<wsdl:part name="parameters" element="typens:catalogProductAttributeCreateResponseParam" />
</wsdl:message>
<wsdl:portType name="{{var wsdl.handler}}PortType">
<wsdl:operation name="catalogCategoryCurrentStore">
<wsdl:documentation>Set_Get current store view</wsdl:documentation>
<wsdl:input message="typens:catalogCategoryCurrentStoreRequest" />
<wsdl:output message="typens:catalogCategoryCurrentStoreResponse" />
</wsdl:operation>
--- 1903,1923 ----
<wsdl:message name="catalogProductAttributeCreateRequest">
<wsdl:part name="parameters" element="typens:catalogProductAttributeCreateRequestParam" />
</wsdl:message>
<wsdl:message name="catalogProductAttributeCreateResponse">
<wsdl:part name="parameters" element="typens:catalogProductAttributeCreateResponseParam" />
</wsdl:message>
+
+ <!-- Added by Matt Johnson 2012-11-09 to fix VS 2010 support of SOAP reference -->
+ <wsdl:message name="catalogProductAttributeRemoveRequest">
+ <wsdl:part name="parameters" element="typens:catalogProductAttributeRemoveRequestParam" />
+ </wsdl:message>
+ <wsdl:message name="catalogProductAttributeRemoveResponse">
+ <wsdl:part name="parameters" element="typens:catalogProductAttributeRemoveResponseParam" />
+ </wsdl:message>
+
<wsdl:portType name="{{var wsdl.handler}}PortType">
<wsdl:operation name="catalogCategoryCurrentStore">
<wsdl:documentation>Set_Get current store view</wsdl:documentation>
<wsdl:input message="typens:catalogCategoryCurrentStoreRequest" />
<wsdl:output message="typens:catalogCategoryCurrentStoreResponse" />
</wsdl:operation>
***************
*** 2760,2771 ****
<soap:body use="literal" />
</wsdl:input>
<wsdl:output>
<soap:body use="literal" />
</wsdl:output>
</wsdl:operation>
</wsdl:binding>
<wsdl:service name="{{var wsdl.name}}Service">
<wsdl:port name="{{var wsdl.handler}}Port" binding="typens:{{var wsdl.handler}}Binding">
<soap:address location="{{var wsdl.url}}" />
</wsdl:port>
</wsdl:service>
--- 2789,2814 ----
<soap:body use="literal" />
</wsdl:input>
<wsdl:output>
<soap:body use="literal" />
</wsdl:output>
</wsdl:operation>
+
+
+ <!-- Added by Matt Johnson 2012-11-09 to fix VS 2010 support of SOAP reference -->
+ <wsdl:operation name="catalogProductAttributeRemove">
+ <soap:operation soapAction="" />
+ <wsdl:input>
+ <soap:body use="literal" />
+ </wsdl:input>
+ <wsdl:output>
+ <soap:body use="literal" />
+ </wsdl:output>
+ </wsdl:operation>
+
+
</wsdl:binding>
<wsdl:service name="{{var wsdl.name}}Service">
<wsdl:port name="{{var wsdl.handler}}Port" binding="typens:{{var wsdl.handler}}Binding">
<soap:address location="{{var wsdl.url}}" />
</wsdl:port>
</wsdl:service>