ntlm Auth , getting "Unable to respond to any of these challenges: {negotiate=Negotiate}"

Doing ntlm authentication to access a .NET Webservice. 
Unfortunately I am getting:
Unable to respond to any of these challenges: {negotiate=Negotiate}

When I access the site/uri with the browser (safari) I am getting the login-Dialog to authenticate and can then access the webservice.

My auth-code looks alike

...
final NTCredentials ntCredentials = new NTCredentials( "<uid>", "<pw>", "", "<domain>" );
final CredentialsProvider ntCredentialsProvider = new CredentialsProvider() 
{
	public Credentials getCredentials(final AuthScheme scheme, final String host, int port, boolean proxy) throws CredentialsNotAvailableException {
		return ntCredentials;
	}
};
DefaultHttpParams.getDefaultParams().setParameter( "http.authentication.credential-provider", ntCredentialsProvider );
...

Also trying to force NTML-only (in order to omit negotiation) fails:
...
// force NTLM
DefaultHttpParams.getDefaultParams().setParameter( "http.protocol.handle-authentication", false );
List<String> authpref = new ArrayList<String>();
authpref.add( AuthPolicy.NTLM );
DefaultHttpParams.getDefaultParams().setParameter( "http.auth.target-scheme-pref", authpref );
DefaultHttpParams.getDefaultParams().setParameter( "http.auth.proxy-scheme-pref", authpref );        
...

It used to work before the endpoint was moved to another host. There I would/did see (in the log/console):
- ntlm authentication scheme selected

What can I do to narrow down this problem?