I found an earlier issue (https://www.virtualmin.com/node/9300) that basically described the error I encountered but it didn't have a fix.
Rather than attempting to upgrade my old server (Ubuntu14.04) I am creating a new Ubuntu 16.04 instance and will then migrate my Virtualmin settings and sites across to the new server.
I created a new Ubuntu 16.04 server and ran the Virtualmin install script (copied from licences section).
I then completed the normal setup steps in the browser.
At this point, I went to Restore Backups and copied the (working) S3 backup details from the old server.
It was at this point Virtualmin informed me that there was a missing Perl module S3::AWSAuthConnect.
I went through this same process when moving from Ubuntu12.04 to Ubuntu14.04 and did not need to install anything myself.
Has something changed in the install or is there something that Virtualmin expects to be installed in the base rather than install it as part of the script?
Hope you can help, Cheers.