This one was tough. Googling pretty fast showed that this problem could be solved by uncommenting the line '$ModLoad imklog' in /etc/rsyslog.conf. This in turn caused kern.log to be filled with messages like 'imklog: error reading kernel log - shutting down: Bad file descriptor'. This in turn is probably caused by some strange interaction between Ubuntu and OpenVZ/virtualization combination, but initially I did not find the precise cause of the problem, nor a solution.
This link finally gives a clue what the problem is and also presents a working workaround:
Following the solution worked for me. In more detail:
Create file /etc/init/kmsg-pipe.conf with the following content:
Then execute the script and restart rsyslogd: