SSH often fails to start after upgrading from Ubuntu 14.04 to 16.04 in virtualised environments. The issue is often that the directory /var/run/sshd is not created during boot. So if you get error messages like "Missing privilege separation directory: /var/run/sshd" you can fix it by adding the following in /etc/rc.local

if [ ! -d /var/run/sshd ]; then
  mkdir /var/run/sshd
  chmod 0755 /var/run/sshd
fi

There are some other workarounds mentioned in the bug report at https://bugs.launchpad.net/ubuntu/+source/systemd/+bug/1811580 but they did not work for me.