That is strange, my web services run fine on both 4.2.x and 5.0. Did you hand-code your WSDL? If so, please post. Otherwise, please post the code for the web service. Also, please post the code for your client.
Figured this one out. It's a class path issue, described here
I use eclipse and with jboss 4.2.2 I could add the server runtime to the client project class path without any problems. That results in the error below if you try on jboss 5.0.0