I would suggest you to use Fiddler
] or even IE developer toolbar to check if what xml values are being sent to the web service.
Then you can be atleast sure that the correct data is sent and there is not issue with the request itself.
If this correct, next step would be to use Visual Studio and debug what do you receive on the web server and step into the constructor (or method). I hope by now, you should already see what's going wrong.