I correlated the nagios logs and the dpkg.log* Files and found out that the last "good" version of snmpd was 5.3.1-8 -- after that, 5.4.1~dfsg-4 was installed and the problems began.