Another piece for the puzzle: Apparently, if I shut down all network related services (NIS, NTP, NFS/automounter) prior to initiating shutdown from within KDE, the machines are much more likely to successfully shut down. No idea why.
Another piece for the puzzle: Apparently, if I shut down all network related services (NIS, NTP, NFS/automounter) prior to initiating shutdown from within KDE, the machines are much more likely to successfully shut down. No idea why.