Rkhunter outputs the following:
System tools
Info: prelinked files found
Performing 'known good' check...
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /bin/cat: at least one of file's dependencies has changed since prelinking
/bin/cat [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /bin/chmod: at least one of file's dependencies has changed since prelinking
/bin/chmod [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /bin/chown: at least one of file's dependencies has changed since prelinking
/bin/chown [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /bin/date: at least one of file's dependencies has changed since prelinking
/bin/date [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /bin/dmesg: at least one of file's dependencies has changed since prelinking
/bin/dmesg [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /bin/env: at least one of file's dependencies has changed since prelinking
/bin/env [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /bin/grep: at least one of file's dependencies has changed since prelinking
/bin/grep [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /bin/kill: at least one of file's dependencies has changed since prelinking
/bin/kill [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /bin/login: at least one of file's dependencies has changed since prelinking
/bin/login [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /bin/ls: at least one of file's dependencies has changed since prelinking
/bin/ls [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /bin/more: at least one of file's dependencies has changed since prelinking
/bin/more [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /bin/mount: at least one of file's dependencies has changed since prelinking
/bin/mount [ BAD ]
/bin/netstat [ OK ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /bin/ps: at least one of file's dependencies has changed since prelinking
/bin/ps [ BAD ]
/bin/su [ OK ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /sbin/chkconfig: at least one of file's dependencies has changed since prelinking
/sbin/chkconfig [ BAD ]
/sbin/ifconfig [ OK ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /sbin/sysctl: at least one of file's dependencies has changed since prelinking
/sbin/sysctl [ BAD ]
/sbin/syslogd [ OK ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/chattr: at least one of file's dependencies has changed since prelinking
/usr/bin/chattr [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/du: at least one of file's dependencies has changed since prelinking
/usr/bin/du [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/file: at least one of file's dependencies has changed since prelinking
/usr/bin/file [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/find: at least one of file's dependencies has changed since prelinking
/usr/bin/find [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/head: at least one of file's dependencies has changed since prelinking
/usr/bin/head [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/killall: at least one of file's dependencies has changed since prelinking
/usr/bin/killall [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/lsattr: at least one of file's dependencies has changed since prelinking
/usr/bin/lsattr [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/md5sum: at least one of file's dependencies has changed since prelinking
/usr/bin/md5sum [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/pstree: at least one of file's dependencies has changed since prelinking
/usr/bin/pstree [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/sha1sum: at least one of file's dependencies has changed since prelinking
/usr/bin/sha1sum [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/stat: at least one of file's dependencies has changed since prelinking
/usr/bin/stat [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/strings: at least one of file's dependencies has changed since prelinking
/usr/bin/strings [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/top: at least one of file's dependencies has changed since prelinking
/usr/bin/top [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/users: at least one of file's dependencies has changed since prelinking
/usr/bin/users [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/vmstat: at least one of file's dependencies has changed since prelinking
/usr/bin/vmstat [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/w: at least one of file's dependencies has changed since prelinking
/usr/bin/w [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/watch: at least one of file's dependencies has changed since prelinking
/usr/bin/watch [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/wc: at least one of file's dependencies has changed since prelinking
/usr/bin/wc [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/whereis: at least one of file's dependencies has changed since prelinking
/usr/bin/whereis [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/who: at least one of file's dependencies has changed since prelinking
/usr/bin/who [ BAD ]
/usr/sbin/prelink: /lib/tls/libc-2.3.4.so has a dependency cycle
/usr/sbin/prelink: /usr/bin/whoami: at least one of file's dependencies has changed since prelinking
/usr/bin/whoami [ BAD ]
/usr/sbin/xinetd [ OK ]
--------------------------------------------------------------------------------
Rootkit Hunter found some bad or unknown hashes. This can be happen due replaced
binaries or updated packages (which give other hashes). Be sure your hashes are
fully updated (rkhunter --update). If you're in doubt about these hashes, contact
the author (fill in the contact form).
--------------------------------------------------------------------------------

The rest of the output looks ok. What exactly does this mean? Should I worry about it?

Thanks!

prelink -au && rpm -e prelink

Prelink sucks, IMHO. A cheap way to optimize the system, but with usually no noticable results and alot of extra work to keep it all prelinked properly.

So, you're saying I should probably not bother with it?