The first thing to be clear on is are your users leveraging on time/off time or Activate Later - these are different features of the tool and would potentially fail for different reasons.
on time/off time is a value that you set in a page's Page Properties, once set you actually publish the content (either through workflow or through the activate button) and the content exists on the publish server. The framework that processes requests however evaluates the on time/off time value at run time and if the the current date and time are before the on time or after the off time it returns a 404 as if the page did not exist. The most likely cause of on time/off time appearing to fail would be a problem flushing dispatcher cache. You can set dispatcher cache flush agents to flush cache as on time/off times are hit but it is possilble for that mechanism to fail, so if you are diagnosing the problem you would want to focus on whether or not a dispatcher flush request was sent at the appropriate time or not. Lots of reasons for this fail but first you want to establish if the request go sent so you can assess whether the problem is at the dispatcher layer or the replication agent layer.
Activate Later works differently - when choose to activate later (or deactivate later) the system actually starts a workflow and and sets up a Sling Schedule Job to kick off at the right time and advance the workflow to actually publish the content. There are any number of reasons this might fail - you will want to look at the workflow history to see if the workflow in question finished abnormally or perhaps went stale - typically though the likely cause of the problem is related to the workflow.
