Tente executar os seguintes comandos nesta ordem:
sudo apt-get update
sudo apt-get dist-upgrade
sudo apt-get update
sudo apt-get install nfs-kernel-server
Isso basicamente forçará a atualização do cache de pacotes, bem como a atualização de outros utilitários do sistema.
Um problema que você pode ter é que você está especificando nfs-common , que recebe a versão mais recente. IIRC, apt preencherá todas as dependências (versões incluídas) automaticamente, mas forçar a instalação de nfs-common instala uma versão muito nova dele.