Hello,
Yesterday I did an apt-get purge and install of rsyslog and since then rsyslog is working again. This both means that my own problem is solved, but also that it will be very hard to diagnose this bug any further. If I can do anything to help, please let me know, but feel free to close this bug.
