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

There are some other workarounds mentioned in the bug report at but they did not work for me.