I b.believe you can work around this either by disabling
preauth_required on principals that need to log in from Solaris or
dropping des3-hmac-sha1 from supported_enctypes in your kdc.conf and
changing passwords.

Both of these work arounds have security implications unfortunately,
although not using des3 probably isn't that serious if you have a lot
of Solaris clients already.