While googling for cool plugins to work with Nagios, I stumbled across this project
http://nagios-aptwatch.alioth.debian.org/ "It can monitor the status of all packages installed on a system via APT. The plugin triggers a warning, when one ore more packages are needed to be upgraded."
