Job failed without starting the SSIS package due to timeout

SSIS package wasn't even started, SQLAgent returned error almost instantly.

It happened once, the job is scheduled to run daily for almost a year now, and until now there wasn't any problem with it. Credentials, data structure weren't changed (we're migrating to another domain, but it didn't affect other jobs using the same proxy).

Error returned by SQLAgent:

Executed as user: <SSIS_PROXY>. Microsoft (R) SQL Server Execute Package Utility  
Version 12.0.4100.1 for 64-bit  
Copyright (C) Microsoft Corporation. All rights reserved.    
Started:  <TIME>  Failed to execute IS server package because of error 0x80131904. 
Server: <SERVER>, 
Package path: <PATH>, Environment reference Id: NULL.  
Description: Timeout expired.  
The timeout period elapsed prior to completion of the operation 
or the server is not responding.  
Source: .Net SqlClient Data Provider  Started:  <TIME>  
Finished: <TIME>  Elapsed:  30.654 seconds.  
The package execution failed.  The step failed.

There are other jobs running in the same time window and they weren't affected. One of them is maintenance job (backup), could that put some exclusive locks on system tables (or whatever) and result in timeout?

Any idea what could've happened?

I was having this error intermittently. On occasion a job that runs fine on a schedule would error and the next interval would run fine. After some research I found that the resources in the SSIS catalog can become locked by other agents starting jobs. The fix that worked for me was to automatically retry 3 times. I have not had the error since.

Hopefully MS will find a way to correct this issue under the hood.

Hope this works for you: https://technet.microsoft.com/en-us/library/ms188952.aspx