SFDC has responded to the case I filed with them. This is what they responded with: 

"There are several possible reasons why your customer would get that message: 

1)For the batch job Start() method (Preparing state), if the initializing query took over 2 minutes to return. For this, the query may need to be made more selective. 
This 

2) If the job did pass the Preparing status and was in Processing status, the logic performed in the execute() method of the affected Batch Apex class may have taken over 20 minutes in a number of attempts. In this case, the immediate workaround is to reduce the batch size. However the solution is to evaluate the amount of work being done during the load and trying to reduce it. If the batch is updating records there is also a consideration around sharing and the order you should process those records: 
o If you process records in no particular order, it is likely there will be lock contention, which will take the process longer. 

o You should focus on ordering the records so that groups of parent records are in the same update call. I.e. when updating contacts, if you do not group by account ID, then multiple accounts need to be locked at the same time. If you order by Account IDs, then the batches that are being updated, have to lock fewer records and will cause potentially less contention). 

o Further best practices can be found at http://www.salesforce.com/us/developer/docs/api_asynch/api_bulk.pdf under the section 'General Guidelines for Data Loads'"