I received this error: "The hostname does not resolve to any configured address." while setting up a Lion OD master on an upgraded Snow Leopard server. After a bit of research, resolved to back up and archive services and perform a clean Lion Server install. After updating to 10.7.4 and confirming DNS to be solid, I still receive the same response.
The server is configured to use DHCP with manual address which includes two DNS servers; the forest root controller and a local DC. I changed to MANUALLY input network info and excluded the local DNS server. This fixed my issue.
It turns out the local Windows domain controller has issues and has been denying access to several network resources (one of them being DNS).