I prefer to install Webmin using the debian package, to be sure to get the latest version. With many of the VPS's I've worked on, there were a few dependencies required before Webmin could be installed and often Ubuntu starts to act froggy with perl dependencies. This is most often what I need to get started:
sudo apt-get install perl libnet-ssleay-perl openssl libauthen-pam-perl libpam-runtime libio-pty-perl apt-show-versions libapt-pkg-perl
Then I move on to wget the latest .deb download and 'dpkg --install xxx_filename.deb' it.