Same situation.  Ubuntu 16.04 openvz vps image of unknown origin.  

Minimized image, ran security updates and rebooted.  openssh server failed to start due to systemd-tmpfiles failing with

    Failed to validate path /var/run/sshd: Too many levels of symbolic links

Which then causes ssh server to fail to start with error:

    Missing privilege separation directory: /var/run/sshd


#
# pre breaking update
#

# uname -a
Linux NJ01 2.6.32-openvz-042stab120.18-amd64 #1 SMP Fri Jan 13 10:33:34 MSK 2017 x86_64 x86_64 x86_64 GNU/Linux

# cat /usr/lib/tmpfiles.d/sshd.conf
d /var/run/sshd 0755 root root

# systemd-tmpfiles --version
systemd 229
+PAM +AUDIT +SELINUX +IMA +APPARMOR +SMACK +SYSVINIT +UTMP +LIBCRYPTSETUP +GCRYPT +GNUTLS +ACL +XZ -LZ4 +SECCOMP +BLKID +ELFUTILS +KMOD -IDN

# systemd-tmpfiles --create /usr/lib/tmpfiles.d/sshd.conf
# # success

# ls -ld /
drwxr-xr-x 23 root root 4096 Feb 26 09:35 /
# ls -ld /var
drwxr-xr-x 12 root root 4096 Nov 26  2016 /var
# ls -ld /var/run
lrwxrwxrwx 1 root root 4 Nov 26  2016 /var/run -> /run
# ls -ld /var/run/sshd
drwxr-xr-x 2 root root 40 Feb 26 09:35 /var/run/sshd

# apt-cache policy systemd
systemd:
  Installed: 229-4ubuntu12
  Candidate: 229-4ubuntu12
  Version table:
 *** 229-4ubuntu12 100
        100 /var/lib/dpkg/status

#---BREAKING UPDATE START----

apt-get update

# "minimize" the system
export DEBIAN_FRONTEND=noninteractive
apt-get --assume-yes install aptitude ubuntu-minimal
aptitude --assume-yes markauto '~i!?name(ubuntu-minimal~|linux-generic~|openssh-server~|systemd)'
aptitude --assume-yes purge '~c'

# apply security updates
apt-get --assume-yes install unattended-upgrades
unattended-upgrade

# reboot
shutdown -r now

#---BREAKING UPDATE END----

# post update (pre-reboot).
# apt-cache policy systemd
systemd:
  Installed: 229-4ubuntu21.16
  Candidate: 229-4ubuntu21.16
  Version table:
 *** 229-4ubuntu21.16 500
        500 http://archive.ubuntu.com/ubuntu xenial-updates/main amd64 Packages
        500 http://security.ubuntu.com/ubuntu xenial-security/main amd64 Packages
        100 /var/lib/dpkg/status
     229-4ubuntu4 500
        500 http://archive.ubuntu.com/ubuntu xenial/main amd64 Packages
# ls -ld /
drwxr-xr-x 23 root root 4096 Feb 26 09:03 /
# ls -ld /var
drwxr-xr-x 12 root root 4096 Nov 26  2016 /var
# ls -ld /var/run
lrwxrwxrwx 1 root root 4 Nov 26  2016 /var/run -> /run
# ls -ld /var/run/sshd
drwxr-xr-x 2 root root 40 Feb 26 09:03 /var/run/sshd
# systemd-tmpfiles --version
systemd 229
+PAM +AUDIT +SELINUX +IMA +APPARMOR +SMACK +SYSVINIT +UTMP +LIBCRYPTSETUP +GCRYPT +GNUTLS +ACL +XZ -LZ4 +SECCOMP +BLKID +ELFUTILS +KMOD -IDN
# systemd-tmpfiles --create /usr/lib/tmpfiles.d/sshd.conf
Failed to validate path /var/run/sshd: Too many levels of symbolic links


Anyway, root cause seems to be this systemd-tmpfiles error.  Tmpfile gets purged at reboot and doesn't get recreated.  

Seems pretty major that applying security updates would lock you out of your server.  If I didn't happen to have a serial console with this particular VPS provider (some others I use don't provide one)...I would have no idea what was going on.

I get this might be due to weird openvz image or older kernel...but these ubuntu openvz images are very common.