A friend of mine in India had some problems with calling a Java web service from .NET 2.0 using web references generated using Visual Studio 2005. Some serialization error occured, but the message was very much useless.
I recommended using WSCF to them and as it turns out the WSCF gave a much more detailed message pinpointing the error to a namespace issue on the Java side.
WSCF is a tool created by Thinktecture supporting the Web Service Contract First approach to developing web services.