Step 1:
Please make sure that Cron is working fine. For this you can install AOE Scheduler
extension.
Step 2:
You need to debug the issue by debugging magento tables. Following tables used for catalog rules:
catalogrule
catalogrule_affected_product
catalogrule_customer_group
catalogrule_group_website
catalogrule_product
catalogrule_product_price
catalogrule_website
You can delete all catalog rules and create one single rule for one product and check following tables:
catalogrule_product
- In this table Magento will manage all product discount percent for all customer group.
catalogrule_product_price
- In this table Magento will manage discounted final price for each product. Here magento will insert three days record for each record. you can check this by "rule_date" field.
If it is work perfectly. Then Again After deleting all Catalog rules again, Please truncate following tables from MySQL.
catalogrule_product
catalogrule_product_price
As due to many records primary key reach on maximum limit and try again by creating rule for 500 products. hope it will start work.
Hope this help!!