We have used a wildcard certificate without issue with a couple of MDM installations.
When you went through the instalation of MDM on the cloud server, what did you put in for the MDM server name? Did you ensure that this was the same UR as used in your SSL Cert (for example if the ssl cert is *.domain.com your MDM server name should be entered as MDM.domain.com (MDM would be the subdomain name given to your public facing address).
I saw something similar to what you are describing and it was because the internal DNS name (mdm.domain.local) was entered during the setup.
The info above is based upon step 8 in the LD MDM Install guide (page 50).
PS This is the wrong section. You've posted this in the Service Desk -> TPS section as opposed to the Management Suite -> Mobility Manager section
The use of a wildcard certificate is fine. You can edit the web.config file in both MDMServer\Program Files (x86)\LANDesk\MDM\Web\DeviceServices and MDMServer\Program Files (x86)\LANDesk\MDM\Web\Enrollment changing all refrences to 'LANDeskMDMServer' to 'LANDeskMDMServer.yourdomain.com'
It's best to make a backup of the web.config file just in case something goes awry when editing.
Pat at Rush-Henrietta Central School District