Sei que você pode alterar a senha do root facilmente ao soltar no prompt do shell de root no menu de recuperação, se você selecionar a opção de recuperação na inicialização. Assim, esses outros usuários podem apenas estar reiniciando o sistema e escolhendo a opção de recuperação na inicialização, caindo para esse prompt e alterando-o de lá sem precisar de acesso root.
Você pode desabilitar isso removendo a entrada de recuperação da lista do grub usando um programa como o grub-customizer , que requer acesso root para executar. Uma vez que esta opção esteja desabilitada, ela removerá a opção do modo de recuperação do grub e evitará pelo menos uma maneira pela qual qualquer usuário pode alterar a senha. Apenas tenha em mente que, se a instalação do Ubuntu parar de funcionar corretamente e precisar das opções de recuperação, você terá que encontrar uma maneira de desfazer essa alteração sem acesso ao terminal (provavelmente por meio de um live CD).
É claro que também pode ser que seu cliente simplesmente escolha adivinhar senhas de raiz que os outros usuários possam encontrar por meio de tentativa e erro. Vale a pena investigar.