Well I got it working but what happened doesn't inspire confidence with Profile Manager.
We had 2 identical Macbook Airs that a husband and wife were using. They were named: GE32344_lastname and GE32346_lastname (same last name).
Profile Manager had them both initially named correctly.
For some reason, a Tech had to re-image the Wifes Mac (a netinstall of 10.9.4). The Tech renamed the newly-imaged Mac incorrectly. The Tech named it the husbands Mac name. Tech could not enroll into Profile Manager and got the error I posted above. I finally got the Mac this morning and started poking around.
I renamed the Mac to the correct name; enrollment failed.
I put a placeholder in Profile Manager using the Serial#; enrollment failed.
I then went to /ProfileManager/mydevices and enrolled the Mac using the self-enrollment way; enrollment SUCCEEDED.
However,
Husbands Mac was now gone from Profile Manager. Wifes Mac was in, named correctly, as a member of all of husbands device groups!
So, I deleted all the profiles from wifes Mac, deleted the device from Profile Manager and rebooted the Mac. I then renamed the Mac something completely different. Standard enrollment (downloading the profiles) succeeded. Husbands Mac is still gone from Profile Manager but at least she is in. I have a call into the Tech for the building the husband works at to try a re-enroll of his Mac.
The device names were very similar, but the S/N/ UUID etc. should have been completely different. Profile Manager should not have had this issue.