you are using Apache AXIS, I see.

You probably don't need to re-write, but you do need (probably) to
re-jigger.  Can we see the WSDL?

Ideally you want the metadata for the service to be something like this:
<service name="Whatever"
         provider="java:RPC"
         style="wrapped"
         use="literal"
         xmlns:ns1="http://example.org/webservices/"

(that should be your deployment descriptor).

This is derived from the WSDL, though.  So you cannot just change the DD
without changing the WSDL.
Since you are following good practice, you have a WSDL defined, and you
used the AXIS WSDL2Java tool to generate a server-side skeleton and
interface, yes?

A working example is here:
http://dinoch.dyndns.org:7070/axis/AboutBasics.jsp

This is a webservices interop sample.  The service is Apache AXIS v1.1 on
JBoss v3.0.2.   The clients are .NET: winforms and webforms (ASP.NET).   The
page includes links to source code, which contains a readme that talks about
the "WSDL First" approach in AXIS.

If you don't want to take away the old webservice, you can maintain 2
parallel interfaces to the same logic.  One will be the old service (RPC
encoded) and another the new one (wrapped/literal) .

-D

binding 'TestServiceSoapBinding' from namespace
'http://172.22.4.130:8080/axis/services/TestService'. Unable to import
operation 'getXML'. The datatype 'Element' is missing.

apachesoap:element.  It basically is returning a XML document which the
program uses.  We are trying to update this program to .NET 1.1.  I am
unable to use wsdl.exe to create a proxy class and I am unable to use the
web service in Visual Studio.  It fails on the apachesoap:element.  Has
anybody experienced this problem?  Are there any solutions to be able to
work around this problem without having to rewrite the web service?  Any
direction would be wonderful!