Are you sure that your new rules are not blocked? Can you give some more details of your rule. Most likely thing is that your criteria is not working as you think and the criteria is never becoming true.
Do you know that in the System Panel -> General Settings you can enable "Rule Manager Debug". This will help you to work out what's going on with your rules.
Hi Daniel, How is the version of your Sdesk ? Would you please take a look at the Scheduled tasks, via admin console -> Business Logic ... only for DB Rules. Another place to see is the Audit Log. You will see when the task was deleted after execution. If you can see any activity then you have problem. So, take a Stop/Start at the Service Desk Server Service. After that , you must see the log messages. The vision of scheduled tasks only shows 1000 entries, but obviously you have more than this. good luck and have a nice weekend... Rgds.