I was facing similar issue and here is what worked for me. I had generated the sei using wsimport.
If the headers are part of the wsdl, you can generate the SEI that accept the headers using -XadditionalHeaders.
If they are not, you will have to add the header programmatically using SOAPHandler. It is simple though!
Here is a link with detailed description. 
http://www.javadb.com/using-a-message-handler-to-alter-the-soap-header-in-a-web-service-client/
Change the method, handleMessage as below
public boolean handleMessage(SOAPMessageContext smc) {
    Boolean outboundProperty = (Boolean) smc.get(MessageContext.MESSAGE_OUTBOUND_PROPERTY);
    if (outboundProperty.booleanValue()) {
        SOAPMessage message = smc.getMessage();
        try {
            SOAPFactory soapFactory = SOAPFactory.newInstance();
            SOAPEnvelope envelope = smc.getMessage().getSOAPPart().getEnvelope();
            SOAPHeader header = envelope.addHeader();
            SOAPHeaderElement se=header.addHeaderElement(new QName("http://schemas.microsoft.com/ws/2005/05/addressing/none", "Action"));
            //se.setMustUnderstand(true); //Ideal way to set if webservice supports
            se.addTextNode("some text");
            se.addAttribute(soapFactory.createName("S:mustUnderstand"),"1"); //S: or s: depending on xmlns
        } catch (Exception e) {
            e.printStackTrace();
        }
    } else {
        try {
            SOAPMessage message = smc.getMessage();
            message.writeTo(System.out);
            System.out.println("");
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }
    return true;
}
//Code to attach handler.
Service1 service1 = new Service1();
        IService1 iService1 = service1.getBasicHttpBindingIService1();
        BindingProvider bindingProvider = (BindingProvider) iService1;
        final Binding binding = bindingProvider.getBinding();
        List<Handler> handlerList = binding.getHandlerChain();
        if (handlerList == null) {
            handlerList = new ArrayList<Handler>();
        }
        handlerList.add(new HeaderHandler());
        binding.setHandlerChain(handlerList);
        ServiceResponse serviceResponse = iService1.callServiceMethod1(serviceRequest);