So I did manage to workout something in my situation to solve this.
The first couple were the basics that everyone always points you towards;
1. Confirm that the DNS you're pointing to has direct forward and reverse mappings for the host/server you're trying to configure. These mappings should be the exact host name you wish to use. In my case I'm behind a route using NAT so I made sure I had, for example, host.domain.com mapped to the local net IP addresses 10.0.1.4 and 10.0.1.3 (being the wired NIC and the wireless interfaces of my Mac Mini).
2. Ran the changeip -checkHostName etc. etc as suggested by all the other posts as well as all the commands in the article OS X Server: How to reset Profile Manager to its original state - Apple Supportconfirming that the hostname was set correctly (and initially it was not. At first I still had host.local).
However, even after those corrections I still had no luck.
Check the Open Directory section of Server.app. I had a master listed there using the old hostname (host.local) instead of the FQDN host.domain.com. Luckily in my case I didn't yet have any data in the directory that I needed to keep and so could just delete it. Once I deleted this directory master I returned to Profile Manager and before turning on Profile Manager I configured Device Management (which all requires an Open Directory) and Server.app completed the correct Open Directory configuration for me.
These were all requirements from the very beginning (since Lion, DNS, hostname, Open Directory and even back then kerberos) that I think as Server.app has simplified some of us have completely forgotten so I hope this helps refresh memories and helps someone new.
