When users are unable to connect, the VPN connection status does not even reach the "verifying username..." dialog, it simply times out and retries.
What is the error code it gives?
My first guess was a DNS problem but if the name resolves correctly with ping then why would it not work with the first VPN attempt. Is it possible that the M0n0 VPN is somehow sleeping untill directly accessed by IP?
Connections work exactly the same whether you connect via DNS or IP. The only difference is on the client, it resolves the DNS hostname to an IP and then connects to that IP. There's no way for m0n0wall to even know whether they're connecting using DNS or IP.
My first guess based on your description is some people are behind stupid/broken/flaky NAT boxes. PPTP uses the GRE protocol which is notorious for having issues with NAT. The people it always works for probably either connect directly with a public IP (no NAT) or use a NAT device that doesn't screw up GRE.