Note that the exploit as posted on security focus has a (not very) subtle deliberate mistake, the consequences of the mistake you are seeing. It only takes a very minor change in the exploit and the person will have root access to your server from a normal user shell account.
So far, there's no fix from Cobalt, though doing this should remove the vulnerability:
chmod 755 /usr/lib/authenticate
Though this may have some consequences as someone reported on the Cobalt list:
"Just been doing some checking, and it seems this 'quick fix' whilst it indeed does fix, also means that some forms of .htaccess don't work, client informed me that webalizer stats access was now nolonger accepting groups as valid users."
So, you, if you still allow user shell access you have a choice of allowing them to get root access, or do the above chmod and risk problems with .htaccess files. I know which problem I'd rather weather
Well I'm the only one with shell access, and the only shell access that is open is SSH. htaccess is extremely important for our server and can not risk being disabled. There seems to be no effect on our server, or any indication that it has been hacked, or attempts towards being hacked.
I just receive that email over and over, that is the only effect I can see. I've looked over that security page you posted and can seem to see any reference to the message I posted above. Anymore info would be great, thanks a bundle.
It is the footprint of this exploit. If you have a look at the exploit code from this link you may be able to see how it works. The message you are receiving is the evidence of this exploit being attempted with fixing the exploit code to run correctly.
To clean this up you can issue:
rm -rf /tmp/core /etc/cron.d/core
It would seem highly likely that someone has access to your server to run this exploit. You should probably install and run something like chrootkit to check your server:
Keep in mind that (as demonstrated previously) it's quite easy for someone with only FTP access to use a script to spawn a shell given CGI or PHP access. So disallowing shell users (which is a smart idea!) isn't a guarantee that you're safe....