If your Drupal cron has failed, and if you see this in your Drupal 6 log, I feel your pain:
Attempting to re-run cron while it is already running.
So what is going on here? Basically, a cron run started and for whatever reason did not finished... and frankly, probably never will. So the first question:
How to I get the Drupal 6 Cron Unstuck?
This is fairly easy to do. There are three easy ways (choose the one that works for you):