FULL PRODUCT VERSION :
I've reproduced the behavior using the following JDKs (all on Linux):

java version "1.5.0_12"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_12-b04)
Java HotSpot(TM) Server VM (build 1.5.0_12-b04, mixed mode)

java version "1.6.0"
Java(TM) SE Runtime Environment (build 1.6.0-b105)
Java HotSpot(TM) Server VM (build 1.6.0-b105, mixed mode)

java version "1.5.0_12"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_12-b04)
Java HotSpot(TM) 64-Bit Server VM (build 1.5.0_12-b04, mixed mode)

java version "1.6.0_14"
Java(TM) SE Runtime Environment (build 1.6.0_14-b08)
Java HotSpot(TM) 64-Bit Server VM (build 14.0-b16, mixed mode)


ADDITIONAL OS VERSION INFORMATION :
Centos 5.3 64 bit

A DESCRIPTION OF THE PROBLEM :
I have a trivial Jaas client which simply attempts to acquire a TGT using a javax.security.auth.login.LoginContext instance.

Using ethereal, I have examined the Kerberos messages sent between the client and the KDC.

When initially acquiring a TGT (with useTicketCache set to false), the initial AS-REQ is rejected as pre-authentication is required. This initial AS-REQ includes all the encryption types (in the KDC_REQ_BODY part of the message) which are configured as being supported in krb5.conf as would be expected.

However when the AS-REQ is resent, including the pre-authentication data (PA-ENC-TIMESTAMP), the encryption types field of the KDC_REQ_BODY section now only includes the encryption type used to encrypt the pre-authentication timestamp.

I believe that this is not correct. The encryption type used for the pre-authentication timestamp is independent/separate to the encryption types field of the KDC_REQ_BODY. It is explicitly specified in the padata section of the message which is separate to the KDC_REQ_BODY. The encryption types of the latter should be the same as in the original message.

For many configurations the problem is not manifest because the encryption type used for pre-authentication is also that used for the TGT (and the session key). This problem is widely misdiagnosed on the web as being related to export security restrictions in the JDK (because the error message is "Message is KDC has no support for encryption type") but this is not the case I believe. A workaround is to remove AES256 and AES128 as encryption types accidentally fixes the problem but I believe it is a protocol implementation issue.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Configure a Kerberos environment.
Verify Kerberos configuration using the MIT "kinit" command line tool.
Compile and run the attached Java source file.
Observe the Kerberos protocol messages using tcpdump or ethereal.

Note that the client MAY successfully authenticate depending on the KDC and the local krb5.conf. To demonstrate the "Message is KDC has no support for encryption type" error: ensure that aes256 is configured in krb5.conf and that the KDC supports aes256 but also ensure that the encryption used for the TGS is NOT aes256. In this case the (Java) client will use AES256 for the preauthentication but will claim that it only supports AES256 in the pre-authenticated AS-REQ which will result in the KDC rejecting the request. The easiest way to replicated this is to used a Windows KDC which by default is set up like this.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
I was expecting to see a similar (Kerberos protocol) exchange to the one I could observe using kinit on the command line.
ACTUAL -
The AS-REQ containing the pre-authentication data contains an incorrect etype value in its KDC-REQ-BODY.

ERROR MESSAGES/STACK TRACES THAT OCCUR :
The KDC's response to the incorrect pre-authenticated AS-REQ will be a KRBError code 14. In a Java client this will typically appear as:
javax.security.auth.login.LoginException: KDC has no support for encryption type (14)
        at com.sun.security.auth.module.Krb5LoginModule.attemptAuthentication(Krb5LoginModule.java:696)
        at com.sun.security.auth.module.Krb5LoginModule.login(Krb5LoginModule.java:542)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
        at java.lang.reflect.Method.invoke(Method.java:597)
        at javax.security.auth.login.LoginContext.invoke(LoginContext.java:769)
        at javax.security.auth.login.LoginContext.access$000(LoginContext.java:186)
        at javax.security.auth.login.LoginContext$5.run(LoginContext.java:706)
        at java.security.AccessController.doPrivileged(Native Method)
        at javax.security.auth.login.LoginContext.invokeCreatorPriv(LoginContext.java:703)
        at javax.security.auth.login.LoginContext.login(LoginContext.java:575)
        at Client.main(Client.java:35)
Caused by: KrbException: KDC has no support for encryption type (14)
        at sun.security.krb5.KrbAsRep.<init>(KrbAsRep.java:66)
        at sun.security.krb5.KrbAsReq.getReply(KrbAsReq.java:449)
        at sun.security.krb5.Credentials.sendASRequest(Credentials.java:406)
        at sun.security.krb5.Credentials.acquireTGT(Credentials.java:378)
        at com.sun.security.auth.module.Krb5LoginModule.attemptAuthentication(Krb5LoginModule.java:662)
        ... 12 more
Caused by: KrbException: Identifier doesn't match expected value (906)
        at sun.security.krb5.internal.KDCRep.init(KDCRep.java:133)
        at sun.security.krb5.internal.ASRep.init(ASRep.java:58)
        at sun.security.krb5.internal.ASRep.<init>(ASRep.java:53)
        at sun.security.krb5.KrbAsRep.<init>(KrbAsRep.java:50)



REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import javax.security.auth.login.LoginException;
import javax.security.auth.login.LoginContext;
import javax.security.auth.login.Configuration;
import javax.security.auth.login.AppConfigurationEntry;
import javax.security.auth.Subject;

import com.sun.security.auth.callback.TextCallbackHandler;

import java.util.Map;
import java.util.HashMap;

/**
 * This JaasAcn application attempts to authenticate a user and reports whether or not the
 * authentication was successful.
 */
public class Client {

    public static void main(String[] args) {
        String applicationName = "simple Jaas test app";
   
        // set java security system properties:
        System.getProperties().setProperty("sun.security.krb5.debug", "true");

        try {
            LoginContext context = new LoginContext
            (
                applicationName,
                new Subject(),
                new TextCallbackHandler(),
                new LoginConfiguration(applicationName)
            );

            context.login();
            System.out.println("Authentication succeeded! - subject:" + context.getSubject());

        } catch (LoginException e) {
            e.printStackTrace();
            System.exit(-1);
        } catch (SecurityException e) {
            e.printStackTrace();
            System.exit(-1);
        }

    }
}

/**
 * Programaticly configure of Jaas rather than relying on an external jaas.conf file in order to
 * make this test case self-contained.
 */
class LoginConfiguration extends Configuration {
    private String applicationName;

    public LoginConfiguration(String applicationName) {
        this.applicationName = applicationName;
    }

    public AppConfigurationEntry[] getAppConfigurationEntry(String name) {
        if (name.equals(applicationName)) {
            return new AppConfigurationEntry[] { new KerberosConfigurationEntry() };
        } else {
            return null;
        }
    }

    public void refresh() {
    }
}

class KerberosConfigurationEntry extends AppConfigurationEntry {
    public KerberosConfigurationEntry() {
        super("com.sun.security.auth.module.Krb5LoginModule", LoginModuleControlFlag.REQUIRED, createOptions());
    }

    private static final Map<String, String> createOptions() {
        HashMap<String, String> options = new HashMap<String, String>();
        options.put("useTicketCache", "false");
        return options;
    }
}

---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
One workaround is to play with KDC configuration until the encryption type chosen by the Java client for creating pre-authentication data matches those used by the TGT.

Another (with a Windows KDC) is to remove AES256 adn AES128 from krb5.conf so that the client is forced to use Arcfour for the pre-authentication data which happens to match the encryption used for the TGT.

Neither are possible workarounds in my organisation; the production Kerberos infrastructure has been verified and is provided "as-is".