How do I Authenticate with SAAJ in a SOAP Request?

Question

I'm using this awesome example here to create a simple SAAJ Soap Client to the IBM Watson Explorer Soap Webservice.

Working Soap client example

But I can't get authentication working.

In the createSOAPRequest method call just add...

...
MimeHeaders headers = soapMessage.getMimeHeaders();
String encoded = new sun.misc.BASE64Encoder().encode((username+":"+password).getBytes());
String authString = "Basic " + encoded;
headers.addHeader("Authorization", authString);
headers.addHeader("SOAPAction", soapAction);
soapMessage.saveChanges();
...

But this won't work. I've tried many permutations of this code. Am I doing something wrong? Also how do I know the service wants the BASE64Encoder?