Hey Naor,
There could be any number of causes, but the most likelyy scenario if you Marketo LP CNAME is new is that that CNAME is not available in the local DNS of these users. You can test by going to the command line on one of the local machines and using nslookup like so:
'nslookup your.cname.com'
This will show if the CNAME is resolving on the local machine.