I've come up against this a few times. In Drupal 6 If you don't use drush you can fix it like this:
1 Remove the cron_% variables from the variables table.
SELECT * FROM variable WHERE name like "cron%";
DELETE FROM variable WHERE name like "cron%";
2 clear Drupal cache at: /admin/settings/performance
by pressing the 'clear cached data' button at the bottom of the page.
3 run cron from command line.admin panel (it needs to be done/admin/reports/status/run-cron don't run it from commandcomand line as if it is done via wget or on the site it will most likely time out)
cd <root of drupal>
php cron.php
NOTE: Don't worry about any PHP Notice: "Undefined index:" or parse errors from cron script. Allow the script to complete, it could take some time.
Once the script has completed you should see "Cron run completed." in drupal dblog messagesthis can cause problems.
4 Check that the next automatic cron run completes as normal.