So I just wasted half of a day on this, and at least for my own system I figured it out *without* doing a clean install.
1. First, check that you have opened the ports as suggested by others here.
2. If you've done that, then the problem may be a rogue entry in your DNS server setting. What that means is if you initially set up your server app with one name, then later switched it to a new one, the old name is still "hanging around" causing havoc. This was the problem. To fix, you can try the steps below. WARNING: this will wipe your open directory. Make a full backup! I'm not 100% sure that wiping your OD is necessary, but it worked for me. Turn off any services you're running.
3. Download the 10.7 server admin tools here: http://support.apple.com/kb/DL1419
4. Open up the WorkGroup manager, and select any network users you've created, then export them. You're backing them up because you're going to wipe your open directory.
5. Open Server Admin.app. Click on the reveal triangle for your server, and it will show an entry for "Open Directory". Click on that.
6. Click on the Settings gear in the top of the right panel.
7. Where it says Role: Open Directory Master, hit Change....
8. In the panel that pops up, hit "set up a standalone directory". It will warn you that it's going to wipe your server open directory data.
9. Now, on the left side of the same screen, select DNS, then hit the "zones" button on top.
10. Look for your old host name(s) there. Select any extra entries that have your old host names, and remove. DO NOT REMOVE your current name entry (the Primary Zone) or the reverse entry (Reverse Zone). If you remove those, you'll be totally hosed. Only remove redundant entries.
11. Back in the Server.app, go to the menu and select Manage -> Manage Network Accounts. It will ask you for some information as it sets up open directory again for you. Give it what it needs.
12. To re-import your saved account info, go to Manage -> Import Accounts From File. (I have not tried this step, but it *should* work. YMMV).
13. Now, go reactivate your profile manager, turn on device management. It should "think" for a bit while it churns through the new open directory data.
14. Now, it should work!!! (at least it does for me). I speculate that the name lookup was getting conflicting results from DNS, causing problems and confusion. This seems to have fixed it.
15. If that doesn't work, one other step I took (but it didn't seem to help by itself) was to wipe the device manager database. To do that, open a terminal and use
sudo /usr/share/devicemgr/backend/wipeDB.sh
WARNING: this will wipe any device info that you've set up. I don't think this is necessary, but might be used as a last ditch effort.
Hope that helps!