As you are most likely aware the way profile manager applies these push settings is not to directly send these to the devices but to apple central servers. This intern will push these back down towards your clients.
The first thing to check will be to ensure these apple macs have a reliable internet connection.
The other possibility I have come across is each mac will need to have the initial trust profile installed and enrolled under a particular user (Say a dedicated service account for the Apple Device such as "appleadmin").
Regards,
A