Não tenho certeza, mas acho que quando você instalou o webmin, ele assumiu a senha antiga do root (aquela que veio com o ubuntu e que ninguém sabe). Mesmo alterando a senha do sistema, vc não altera a do webmin.
Tente desintalar o webmin (desinstalação completa, inclusive com arquivos de configuração) e instale novamente.
Acho que deve funcionar, porque comigo funcionou assim.
Claro que deve existir outra maneira mais simples (tipo, editando algum arquivo de configuração do webmin diretamente) mas eu não conheço.