It seems that the exception is in the wiring of the service reference. If the service side throws any error and its not getting passed to thec client, you need to put
includeExceptionDetailsInFaults = true
for the serviceDebug attribute in server side configuration.
I believe that the service atleast gets hit by the client. However, to debug this scenario, try to load your service through browser and manually hit the method. If it returns fine, then the issue is in client side configuration. By including this attribute, you can be more clear about what's happening.
Also update your service reference once so that you are sure that you have a latest copy of wsdl just in case you updated the service after creating the service reference.
Once you get the actual stack trace, identify the points where it shows about the application (ignore the framework lines) and the post those.