package rsyslog 8.16.0-1ubuntu3 failed to install/upgrade: subprocess installed post-installation script returned error exit status 1

Rsyslog got removed for testing syslog-ng (in a quite fresh Ubuntu Mate 16.04 installation). This removes also the meta-package ubuntu-minimal (why this nonsense?). But then syslog-ng got removed and rsyslog re-installed. It seems that the installation of rsyslog fails then repeatedly. The installation of ubuntu-minimal works (no rsyslog installation errors) but after a reboot the starting of rsyslog fails with the message that the installation failed.

ProblemType: Package
DistroRelease: Ubuntu 16.04
Package: rsyslog 8.16.0-1ubuntu3
ProcVersionSignature: Ubuntu 4.4.0-47.68-generic 4.4.24
Uname: Linux 4.4.0-47-generic x86_64
ApportVersion: 2.20.1-0ubuntu2.1
Architecture: amd64
Date: Mon Nov 28 11:20:45 2016
ErrorMessage: subprocess installed post-installation script returned error exit status 1
InstallationDate: Installed on 2016-11-27 (1 days ago)
InstallationMedia: Ubuntu-MATE 16.04 LTS "Xenial Xerus" - Release amd64 (20160420.1)
RelatedPackageVersions:
 dpkg 1.18.4ubuntu1.1
 apt 1.2.15
SourcePackage: rsyslog
Title: package rsyslog 8.16.0-1ubuntu3 failed to install/upgrade: subprocess installed post-installation script returned error exit status 1
UpgradeStatus: No upgrade log present (probably fresh install)