Brand New Mac Mini with OS X Server, Open Directory not working
I had the same problem initially too. But for many months now, though, Open Directory has been working as expected and serves our many users' credentials reliably.
It was only after the following that Open Directory settled down:

I was 100% sure that the OS X Server's DNS and reverse DNS was consistent, as viewed from within and without our network, and
that the DNS records matched exactly the domain name on the SSL Certificate we purchased.

If there are any inconsistencies between these, then the Server app just can't make all the assumptions about its identity that it needs to.
If all this sounds simple - we did not find it so.
This was our experience after several failed attempts and several attempts where we thought things were working but Open Directory flaked out. Yours will be different e.g. if your OS X Server is not internet-facing:

Important Note: All this had to be done on OS X before the Server app was installed successfully and running reliably. This will require special attention if you bought a Mac Mini with Server included. You have to get the OS X identity issues sorted before you go ahead with the step of installing the OS X Server app. It's installation is quite brilliant ... if all its (few) assumptions are met; but can cause a right mess if they aren't!
I had to double and triple check before I realised that I had not told the people selling me our fixed IP Addresses (BT in the UK) the correct FQDN to resolve reverse DNS to.
We decided to use OS X Server's DNS to manage all the domains we manage. So, in the case of our Server's FQDN, we had to tell BT to delegate the DNS to our OS X Server's IP Address.
These interactions with external parties can take from many hours to a few days and should be completed to your satisfaction before you unwrap the Server app. Don't expect instant installation of Server until this is all sorted.
I had to play games with the router to have OS Server's external FQDN name on the local network. In our case (BT Business Hub 3) we had OS X connect to the router with DHCP but the router was set to give OS X the correct external fixed IP Address. This is a quirk with this particular router. Normally you are recommended to use OS X System Preferences Network Settings a fixed IP address; in our case we had to allow the router to give it a fixed IP address.
All this had to be done before OS X Server was installed successfully

An ideal place to start
The perennial advice - that still stands - is to start by running sudo changeip -checkhostname
(Although, ironically, I don't think changeip is there until afer you've installed Server ... so maybe it's only ideal after you've already got things right!)
When you can: run sudo changeip -checkhostname make sure you get the response:

...
The names match. There is nothing to change.
dirserv:success = &quot;success&quot;

and make sure that Current HostName value == the name on your SSL Certificate == the name on the front page of the Server app GUI
Open Ports
Another thing: ensure that your Server can be reached by the ports that it needs. These can be more than you might imagine. I just did this port scan (using the Network Utility on my MacBook) of our Server and you can see what ports it has open to provide its services. See  also Apple support page for Well Known Ports
Port Scan has started…

Port Scanning host: 81.123.123.123

     Open TCP Port:     22          ssh
     Open TCP Port:     25          smtp
     Open TCP Port:     53          domain
     Open TCP Port:     80          http
     Open TCP Port:     88          kerberos
     Open TCP Port:     106         3com-tsmux
     Open TCP Port:     110         pop3
     Open TCP Port:     143         imap
     Open TCP Port:     311         asip-webadmin
     Open TCP Port:     389         ldap
     Open TCP Port:     443         https
     Open TCP Port:     464         kpasswd
     Open TCP Port:     587         submission
     Open TCP Port:     625         dec_dlm
     Open TCP Port:     636         ldaps
     Open TCP Port:     749         kerberos-adm
     Open TCP Port:     993         imaps
     Open TCP Port:     995         pop3s
     Open TCP Port:     1640        cert-responder
     Open TCP Port:     3659        apple-sasl
     Open TCP Port:     4190        sieve
     Open TCP Port:     5900        rfb
     Open TCP Port:     7654
     Open TCP Port:     8008        http-alt
     Open TCP Port:     8443        pcsync-https
     Open TCP Port:     8800        sunwebadmin
     Open TCP Port:     8843
Port Scan has completed…