Em suma, sim. Você deve atualizar para o Ubuntu 14.04 primeiro, depois atualizar novamente para o 16.04. Essa é a maneira correta de fazer as coisas.
Se você tiver acesso físico ao servidor, poderá carregar 16.04 em uma unidade USB, inicializá-lo e atualizá-lo diretamente.