Purge `nagios3`. Then reinstall. That will probably work.
apt-get purge nagios3
apt-get install nagios3
The purge will get rid of the config files, which the system didn't delete initially, and so thought were still installed. If purging `nagios3` is not an option, then it will be a little more complicated. If that is the case, leave a comment.