Can not install openssh-server on Ubuntu 16.04

Try to perform a apt update before :

apt-get clean
apt-get update
apt-get install openssh-server

I was getting the same error and I didn't need to change the server.

I was getting the exact same error.

In the Software & Updates changing the server from my local country to Main server, and also adding the Canonical Partners from the "Other Software" tab helped installing the openssh-server in my case. I am not sure which of the two helped.

I had the same problem. I fixed it by uninstalling the openssh-client and then installing openssh-server.

sudo apt-get remove openssh-client
sudo apt-get autoclean 
sudo apt-get install openssh-server