Next time one of them tells you it won't play, ask them what happens when they try. Do they get an error message (and if so, what is it)? Or does the disc just go unnoticed? And these same users, are they able to play other DVDs on those same Macs?
Also, you specified Mac laptops. Does this mean that Mac desktop users were okay?
Lots of newer players aren't so picky, but some are. My old Apex 1200 would play almost any video file on any disc, even stuff downloaded from the 'net and burned to a CD-R. However, put a DVD without the AUDIO_TS folder in it and it would sit and spin forever without recognizing the disc.
The newer Magnavox DVD recorders i've got don't care about the AUDIO_TS folder, but they won't play much of anything besides DVDs.