Just to add on to this thread for posterity — you can also use the Webservice Helper tool from http://www.jool.nl/new/
This is a web application which lets you build your service using a class -> WSDL method, instead of the other way around.
I had the SOAP service up and running in about half an hour using this tool. Very handy.