It took me a little bit to figure out what the problem was ...

Here's a minimal test case:

use SOAP::Lite;
my $VAR = bless( {
  'keys' => bless( [
    'name',
    'addr',
    'phone'
  ], 'string' ),
  'values' => bless( [
    'bubba',
    'home',
    '555-1212'
  ], 'string')
}, 'HashMapBean' );

my $xml = SOAP::Serializer->serialize($VAR);
[download]

Because you've cast the array as a 'string', it's calling the 'as_string' method, which doesn't like references. You'd have to cast each one individually as strings ... which you can't do, because they're not references. But you don't actually have to cast items as strings (which you need to use SOAP::Data for), unless isn't something that SOAP::Lite might incorrectly guess on (eg, if it's all digits, it'll look like a number, and might be cast as an int)

use SOAP::Lite;
my $VAR = bless( {
  'keys' => bless( [
    'name',
    'addr',
    'phone'
  ], 'ArrayOf_xsd_string' ),
  'values' => bless( [
    'bubba',
    'home',
    '555-1212'
  ], 'ArrayOf_xsd_string')
}, 'HashMapBean' );

my $xml = SOAP::Serializer->serialize($VAR);

print "\n$xml\n\n";
[download]

You can also find good information on dealing with more complex structures in SOAP::Lite at Byrne Reese's website