Nesting elements is actually a bit tricky. This article I wrote a while ago for builder.com.com (why on earth is their domain dotcom-dotcom? how innane) discusses this topic in much more detail. But here is the short answer:
SOAP::Data->name('foo' => \SOAP::Data->value(SOAP::Data->name('bar' => '123'))
In a nutshell, the above code will produce the following XML:
The trick is dereferencing the nested SOAP::Data element (shown in bold above). Doing so is very unintuitive, but it works.