Nagios does not come with CentOS but is available via rpmforge (where you probably installed it from in the first place)
You need to replace the RHEL4 rpmforge repo with the RHEL5 one, like so:
$ rpm -Uhv
http://apt.sw.be/redhat/el5/en/i386/rpmforge/RPMS/rpmforge-release-0.3.6-1.el5.rf.i386.rpmNotice that rpm did not overwrite the .repo file, but this is what we want:
$ mv /etc/yum.repos.d/rpmforge.repo.rpmnew /etc/yum.repos.d/rpmforge.repo
Flush the cache
$ yum clean all
...and try again :-)
$ yum update nagios nagios-plugins
Don't forget to update the plugins^^
One more thing: You may need to check your resource.cfg since some versions of Nagios set USER2 to 'plugins/eventhandler', other versions use 'plugins/contrib'. If some of your plugins stop working, this is probably why.