I had this happen with Server 4.0 when we started with it. The Profile Manager seemed a bit touchy and did not work until I had tried several times. I did not fight with anything the computer said was broken.
I destroyed the entire Profile Manager several times before everything took. OS X Server: How to reset Profile Manager to its original state - Apple Support. We use a self signed certificate so I know that works. I'm sure you have followed up on it due to the error but obviously make sure your certificate is in a valid date range. Do you have the ability to try having the server be server.company.com in DNS rather than server.local? server.company.com is how my working server appears in DNS so I know that works too. In the past, that has been an issue for other services.
Each time I got that error I started over with the machine I was working on. I manually removed all installed items from the client, removed the client from My Devices list on the server, rebooted everything, and tried again. Eventually things worked despite following the same procedure several times.
Not an exact solution but I was able to get it to work eventually.
-Erich
