HTTP basic authentication through CXF interceptor not working

I'm having some trouble setting the HTTP Authorization header for a web service request using Apache CXF. I have my client setup through spring:

<bean id="loggingInInterceptor" class="org.apache.cxf.interceptor.LoggingInInterceptor" />
<bean id="loggingOutInterceptor" class="org.apache.cxf.interceptor.LoggingOutInterceptor" />

<bean id="myHTTPAuthInterceptor" class="my.app.MyHTTPAuthInterceptor" autowire="constructor" />

<bean id="webServiceFactory" class="my.app.WebServiceFactory">
    <property name="wsdlLocation" value="classpath:/my/app/webservice.wsdl" />
    <property name="serviceURL">
        <jee:jndi-lookup jndi-name="webservice/url" />
    </property>
    <property name="inInterceptors">
        <list>
            <ref bean="loggingInInterceptor" />
        </list>
    </property>
    <property name="outInterceptors">
        <list>
            <ref bean="loggingOutInterceptor" />
            <ref bean="myHTTPAuthInterceptor" />
        </list>
    </property>
</bean>

<bean id="myWebService" factory-bean="webServiceFactory" factory-method="getInstance" />

Headers are set through MyHTTPAuthInterceptor like this:

public MyHTTPAuthInterceptor(ConfigDao configDao)
{
    super(Phase.POST_PROTOCOL);

    this.configDao = configDao;
}

@Override
public void handleMessage(Message message) throws Fault
{
    Map<String, List<?>> headers = (Map<String, List<?>>) message.get(Message.PROTOCOL_HEADERS);

    String authString = configDao.getUsername() + ":" + config.getPassword();
    headers.put("Authorization", Collections.singletonList("Basic " + new String(Base64.encodeBase64(authString.getBytes()))));
}

With username and both set to 'test', everything seems to be OK in the logs:

Headers: {SOAPAction=[""], Accept=[*/*], Authorization=[Basic dGVzdDp0ZXN0]}

However, the server returns a HTTP 401: Unauthorized.

Not knowing what's going wrong, I took a whole other approach by changing my web service client factory code. I added a basic authorization policy to the client's conduit like this:

HTTPConduit httpConduit = (HTTPConduit) client.getConduit();
AuthorizationPolicy authorizationPolicy = new AuthorizationPolicy();
authorizationPolicy.setUserName("test");
authorizationPolicy.setPassword("test");
authorizationPolicy.setAuthorizationType("Basic");
httpConduit.setAuthorization(authorizationPolicy);

Tested my setup again, same log (different order though):

Headers: {SOAPAction=[""], Authorization=[Basic dGVzdDp0ZXN0], Accept=[*/*]}

Now the server's response is 200 OK!

Problem solved you might think, but the second approach doesn't really work for me. My application is a multi-tenant environment, all with different username and password. With the second approach I cannot reuse my client.

How can I get my interceptor to work correctly? Am I plugging into the wrong phase? Does the order of the headers matter? If so, how do I change it?