Kerberos says there is no KDC at the server’s location while getting initial credentials

This is probably some stupid error I've overlooked, but I've been working on this on and off for about a week.

Running version 1.10.3 release 17.fc18

This is my krb5.conf

[logging]
default = FILE:/var/log/krb5libs.log
kdc = FILE:/var/log/krb5kdc.log
admin_server = FILE:/var/log/kadmind.log

[libdefaults]
default_realm = KERBEROS.INTERNAL.COM

[realms]
KERBEROS.INTERNAL.COM = {
   default_domain = kerberos.internal.com
   kdc = kerberos.internal.com:
   admin_server = kerberos.internal.com:
}

I know the DNS is working correctly

$ host kerberos.internal.com
kerberos.internal.com has address 10.8.0.1

And the server is running

krb5kdc.service - Kerberos 5 KDC
   Loaded: loaded (/usr/lib/systemd/system/krb5kdc.service; enabled)
   Active: active (running) since Tue 2013-06-25 21:42:07 EDT; 10min ago

But this still happends

$ kinit -V kadmin/admin
Using default cache: /tmp/krb5cc_0
Using principal: kadmin/admin@KERBEROS.INTERNAL.COM
kinit: Cannot contact any KDC for realm 'KERBEROS.INTERNAL.COM' while getting initial credentials

And this

$ kadmin -p kadmin/admin
Authenticating as principal kadmin/admin with password.
kadmin: Cannot contact any KDC for requested realm while initializing kadmin interface

Is it just some stupid mistake, or did I screw up the installation or something? I've messed around with DNS options a bit, and I don't think they make much of a difference. It is definitely accepting connections, and the journal shows absolutley nothing.