When configuring Mac OS X Server 10.3 or later as an Open Directory Master, the Kerberos Domain Controller (KDC) won't start without proper DNS setup.
The server should have both forward and reverse DNS records. You can verify this by issuing the following command in the Terminal, at the server, before configuring it as an Open Directory Master.
# host <name/address>
In place of <name/address>, type the IP address or fully qualified domain name (FQDN) of the server. Whichever one you type, it should return the other. If it doesn't work on both directions, DNS isn't set up properly for your server.
If your DNS is running on Mac OS X Server, you can learn more about it in the DNS section of the Network Services guide found here. If your DNS is on another platform, consult the appropriate resources or the system administrator.