Update:
I did get the

use MarketSeg;

print MarketSeg::GetMarketClassifiers('Main Exec');
[download]

to work. The code generated by stubmaker.pl contained this:

my %methods = (
  RpcGetMarketClassifiers => {
    endpoint => 'http://webservices.seek.com.au/marketsegment.asmx',
    soapaction => 'http://webservices.seek.com.au/RpcGetMarketClassifi
+ers',
    uri => 'http://webservices.seek.com.au',
    parameters => [
      SOAP::Data->new(name => 'marketSegment', type => 's:string', att
+r => {}),
    ],
  },
  GetMarketClassifiers => {
    endpoint => 'http://webservices.seek.com.au/marketsegment.asmx',
    soapaction => 'http://webservices.seek.com.au/GetMarketClassifiers
+',
    uri => '',
    parameters => [
      SOAP::Data->new(name => 'parameters', type => '', attr => {}),
    ],
  },
);
[download]

Not sure what's the Rpc... version supposed to be good for, but if I copy the parameters => [...] from the RpcGetMarketClassifiers to the GetMarketClassifiers it starts to work. Erm, OK.