I am trying to make a SOAP call out but getting an error because of the request xml has been constructed. The server side wants every header elements (user name, password, security token) to have a namespace (header schema) but the Apex generated does have a name space for every element but embeded under header element. please see the below requests:

Required Request:

<env:Envelope xmlns:env="http://schemas.xmlsoap.org/soap/envelope/" xmlns:head="http://services.xx.com/schema/common/header/v01/Header" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
   <env:Header>
      <Header xmlns="http://services.xx.com/schema/common/header/v01/Header">
         <head:UserName>xx</head:UserName>
         <head:Password>xxxxx</head:Password>
         <head:SecurityToken>xxxx</head:SecurityToken>
         <head:Timestamp>2014-07-01T12:14:20.413Z</head:Timestamp>
      </Header>
   </env:Header>
   <env:Body>
      <UpdateCustomerRequest xmlns="http://services.xx.com/schema/bs/customer/v01/MaintainCustomer">
         <Customer>
            <AccountGUID xmlns="http://services.xx.com/schema/common/customer/v01/Customer">xx</AccountGUID>
            <regID xmlns="http://services.xx.com/schema/common/customer/v01/Customer">123</regID>
            <FirstName xmlns="http://services.xx.com/schema/common/customer/v01/Customer">Test</FirstName>
            <LastName xmlns="http://services.xx.com/schema/common/customer/v01/Customer">Phone User</LastName>
            <Gender xmlns="http://services.xx.com/schema/common/customer/v01/Customer">Female</Gender>
         </Customer>
         <HandsetList/>
      </UpdateCustomerRequest>
   </env:Body>
</env:Envelope>

Salesforce generated Request:

<env:Envelope xmlns:env="http://schemas.xmlsoap.org/soap/envelope/" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
   <env:Header>
      <Header xmlns="http://services.xxx.com/schema/common/header/v01/Header">
         <UserName>xxxx</UserName>
         <Password>xxxx</Password>
         <SecurityToken>xxxx</SecurityToken>
         <Timestamp>2014-07-01T12:14:20.413Z</Timestamp>
      </Header>
   </env:Header>
   <env:Body>
      <UpdateCustomerRequest xmlns="http://services.xxx.com/schema/bs/customer/v01/MaintainCustomer">
         <Customer>
            <AccountGUID xmlns="http://services.xxx.com/schema/common/customer/v01/Customer">001M000000XhiniIAB</AccountGUID>
            <VregID xmlns="http://services.xxx.com/schema/common/customer/v01/Customer">123</VregID>
            <FirstName xmlns="http://services.xxx.com/schema/common/customer/v01/Customer">Test</FirstName>
            <LastName xmlns="http://services.xxx.com/schema/common/customer/v01/Customer">Phone User</LastName>
            <Gender xmlns="http://services.xxx.com/schema/common/customer/v01/Customer">Female</Gender>
         </Customer>
         <HandsetList/>
      </UpdateCustomerRequest>
   </env:Body>
</env:Envelope>

My WSDL generated Interface and header below:

//Generated by wsdl2apex

public class WS_SOA_MaintainCustomerInterface {
    public class MaintainCustomerServiceHTTPBinding {
        public String endpoint_x = 'http://services.xxx.com/wsdl/bs/customer/v01/MaintainCustomerService';
        public Map<String,String> inputHttpHeaders_x;
        public Map<String,String> outputHttpHeaders_x;
        public String clientCertName_x;
        public String clientCert_x;
        public String clientCertPasswd_x;
        public Integer timeout_x;
        public WS_SOA_HeaderInfo.Header Header;
        private String Header_hns = 'Header=http://services.xx.com/schema/common/header/v01/Header';
        private String[] ns_map_type_info = new String[]{'http://services.xx.com/schema/bs/customer/v01/MaintainCustomer', 'WS_SOA_MaintainCustomerType', 'http://services.xx.com/schema/common/customer/v01/Customer', 'WS_SOA_CustomerType', 'http://services.xx.com/wsdl/bs/customer/v01/MaintainCustomerService', 'WS_SOA_MaintainCustomerInterface', 'http://services.xx.com/schema/common/header/v01/Header', 'WS_SOA_HeaderInfo', 'http://services.xx.com/schema/common/handset/v01/Handset', 'WS_SOA_HandsetDetail', 'http://services.xx.com/schema/common/acknowledgement/v01/Acknowledgement', 'WS_SOA_MaintainCustomerAcknowledgement', 'http://services.xx.com/schema/common/service/v01/Service', 'WS_SOA_ServiceInfo'};
        
        public WS_SOA_MaintainCustomerType.UpdateCustomerResponseType updateCustomer(WS_SOA_CustomerType.CustomerType Customer,WS_SOA_HandsetDetail.Handset HandsetList) {
            WS_SOA_MaintainCustomerType.UpdateCustomerRequestType request_x = new WS_SOA_MaintainCustomerType.UpdateCustomerRequestType();
            request_x.Customer = Customer;
            request_x.HandsetList = HandsetList;
            WS_SOA_MaintainCustomerType.UpdateCustomerResponseType response_x;
            Map<String, WS_SOA_MaintainCustomerType.UpdateCustomerResponseType> response_map_x = new Map<String, WS_SOA_MaintainCustomerType.UpdateCustomerResponseType>();
            response_map_x.put('response_x', response_x);
            WebServiceCallout.invoke(
              this,
              request_x,
              response_map_x,
              new String[]{endpoint_x,
              'http://services.xx.com/wsdl/bs/customer/v01/MaintainCustomerService/updateCustomer',
              'http://services.xx.com/schema/bs/customer/v01/MaintainCustomer',
              'UpdateCustomerRequest',
              'http://services.xx.com/schema/bs/customer/v01/MaintainCustomer',
              'UpdateCustomerResponse',
              'WS_SOA_MaintainCustomerType.UpdateCustomerResponseType'}
            );
            response_x = response_map_x.get('response_x');
            return response_x;
        }
    }
}

Header Class:

//Generated by wsdl2apex

public class WS_SOA_HeaderInfo {
    public class Header {
        public String UserName;
        public String Password;
        public String SecurityToken;
        public String Domain;
        public String Role;
        public String MessageID;
        public String TransactionID;
        public DateTime Timestamp;
        
        private String[] UserName_type_info = new String[]{'UserName','http://services.xx.com/schema/common/header/v01/Header',null,'0','1','false'};
        private String[] Password_type_info = new String[]{'Password','http://services.xx.com/schema/common/header/v01/Header',null,'0','1','false'};
        private String[] SecurityToken_type_info = new String[]{'SecurityToken','http://services.xx.com/schema/common/header/v01/Header',null,'0','1','false'};
        private String[] Domain_type_info = new String[]{'Domain','http://services.xx.com/schema/common/header/v01/Header',null,'0','1','false'};
        private String[] Role_type_info = new String[]{'Role','http://services.xx.com/schema/common/header/v01/Header',null,'0','1','false'};
        private String[] MessageID_type_info = new String[]{'MessageID','http://services.xx.com/schema/common/header/v01/Header',null,'0','1','false'};
        private String[] TransactionID_type_info = new String[]{'TransactionID','http://services.xx.com/schema/common/header/v01/Header',null,'0','1','false'};
        private String[] Timestamp_type_info = new String[]{'Timestamp','http://services.xx.com/schema/common/header/v01/Header',null,'0','1','false'};
        private String[] apex_schema_type_info = new String[]{'http://services.xx.com/schema/common/header/v01/Header','true','false'};
        private String[] field_order_type_info = new String[]{'UserName','Password','SecurityToken','Domain','Role','MessageID','TransactionID','Timestamp'};
    }
}

Has someone encountered this problem and possibly give a work around of this problem?