Трудно сказать, что вы пытались при очистке + переустановке, но попробуйте следующее:
sudo dpkg --purge --force-all nginx nginx-common nginx-full
sudo apt-get install nginx
Проблема была решена путем выполнения следующего:
/etc/init.d/rsyslog restart
/etc/init.d/crond restart