I was having lots of issues with WSDL on VisualStudio or NetBeans. I finally tried latest eclipse (3.3) with built-in Apache Axis plugin and it worked like a champ. It creates all the code for you to call the web service. All you have to do, is tell it where is the WSDL and which method to call.
Of course this is in Java, which is very similar to C#.