I found this solution:

Excel 2003 and the WebServices? Toolkit are not set up to pass datasets
back and forth. You can do it but it takes seveal hundred lines of code
to manually parse through the IXMLDOMNodeList? on the Excel end of
things. If you try to send the IXMLDOMNodeList? back to the WebSevice?
it is very very finicky.

The WebService? tool kit for Microsoft Office will receive a dataset as
a IXMLDOMNodeList? object. This object is pretty much useless, and
cannot be used to pass a dataset back to an WebService?.

The way to get around this is to send any datasets back and forth as
XML strings.

On the .Net WebService end of things:
-------------------------------------

TO SEND:
using System.XML;
[WebMethod]
public string sendstuff() {
DataSet ds = new DataSet("Name1");
...
return ds.GetXML();
}
TO RECEIVE
using System.XML;
public int receivestuff(string xmlString){
DataSet ds = new DataSet("Name2");
StringReader stream = new StringReader(xmlString);
ds.ReadXml(stream)
....
return resultCode;
}

On the Excel 2003 side of things:
---------------------------------
Preparation:
-make sure the Microsoft Office Web Services tookit is installed
-go to the Visual Basic Editor (Tools - Macro - Visual Basic Editor)
and from its tools menu go to Web Services References.., in the dialog
box, type in the exact URL for the WebService you are using (that you
wrote as above) and click Search, then check it off and add it
-use the webService to create a sample XML file for each type of XML
string you want to send/receive, save this file so it has the same name
of the DataSet you will use (e.g., Name1.xml and Name2.xml).
-open Excel and install the XML Toolkit Add-In]
-use the XML toolbar to open the "XML Schemas" pane
-Add each of the of the xml files you created as a new map (do not use
an .xsd file to ty to create the XmlMaps - there is a good chance that
the XmlMap created this way will not be exportable)
-map all the elements each of the xml files on its own sheet in your
workbook

-then use the following code:
TO RECEIVE:
Dim ws As clsws_YourWebService
Dim ss As String
Dim xmap As XmlMap
' attach to web service
Set ws = New clsws_YourWebService
' get model parameters
ss = ws.wsm_sendstuff()
'put on spreadsheet
Set xmap = ThisWorkbook.XmlMaps("Name1_Map")
xmap.ImportXml (ss)
TO SEND:
Dim ws As clsws_YourWebService
Dim ss As String
Dim xmap As XmlMap
Dim resultCode As Integer
' attach to web service
Set ws = New clsws_YourWebService
'get references we need from spreadsheet
Set xmap = ThisWorkbook.XmlMaps("Name2")
' create XML string of data
xmap.ExportXml data:=outstr
' call the webservice
resultCode = ws.wsm_receivestuff(outstr)

Anyway, this is what I found worked.

Cheers,
Graham