Problem was, that when running "hostname" in shell, I only got the name, but it had to be the fully qualified name. In addition the KVNO didn't match. To get the KVNO, run getprinc host/<hostname> in kadmin.local on the kdc and run klist -ke on the client.