In Java 6, we have a block of codes to detect what scheme should be chosen which also invalidate some previous authentication states. It seems that if the http.auth.preference system property is set, Java thinks there's no need to performance this detection and the old header was reused, and the server rejects it as a replay. Too bad.