Encountered an issue this week that maybe someone has an answer for. . .
I authored a DVD with a first play movie on it and it would not play on several Mac laptops and 1 G5 Dual 2.0. All Macs were running Panther or Tiger. The first play movie would hesitate and freeze about half-way through and then advance to the main menu.
Played great on my laptop and tower(both winXP), 2 set-top players and a G4 dual 450 Mac running 9.something. Ended up having to take the first play off, for it to play on the clients Macs.
You might try playing some other DVDs with first plays and see how they do on each of the machines you mentioned. If they all run smoothly on the machines giving you trouble, try burning another copy of the DVD and see if it starts working. Could be there was some error in the burn process that some players and/or software can't read through.