SQL Server backup failing. Error: 3041, Severity: 16, State: 1 First of all, I'm very new at stackexchange, so please bear with me.

I'm running a SQL Server 9.0.4060.

My problem is: my SQL Server backup keeps failing on a lot of the databases.

The Maintenance plan runs to different backup jobs:

DIFF backup everyday at 20:30 and FULL backup every Sunday at 20:30.

I get these two errors foreach database that fails to complete the backup:

Date        06-11-2012 20:31:06
Log     SQL Server (Current - 07-11-2012 11:43:00)
Source      Backup
Message
BACKUP failed to complete the command BACKUP DATABASE (dbname) WITH DIFFERENTIAL. Check the backup application log for detailed messages.

Date        06-11-2012 20:31:06
Log     SQL Server (Current - 07-11-2012 11:43:00)
Source      Backup
Message
Error: 3041, Severity: 16, State: 1.


Extra errors.

Date     06-11-2012 17:53:27 
Log      SQL Server (Current - 07-11-2012 11:43:00) 
Source   Logon 
Message  Error: 18456, Severity: 14, State: 16.

Date     06-11-2012 17:53:27 
Log      SQL Server (Current - 07-11-2012 11:43:00) 
Source   Logon 
Message  Login failed for user 'sa'. [CLIENT: &lt;local machine&gt;]

Date     06-11-2012 20:30:11
Log      SQL Server (Current - 09-11-2012 11:27:00)
Source   spid15s
Message
SQL Server has encountered 2 occurrence(s) of cachestore flush for the 'Bound Trees' cachestore (part of plan cache) due to some database maintenance or reconfigure operations.


There are to other similar errors to the one above, with 'SQL Plans' and 'Object Plans'. Instead of 'Bound Trees'.

If you guys need any other information, just say the word.
As Max pointed out, the sa login error doesn't corrolate to the backup time as it happens several hours before, however the 2nd one does.  Have you looked into:
http://blogs.msdn.com/b/sqlprogrammability/archive/2007/01/17/10-0-plan-cache-flush.aspx

http://www.sqlservercentral.com/Forums/Topic377116-146-1.aspx#bm380502

Do any of the items in the MSDN blog play a factor in your environment?  Most common one would be the AUTO_CLOSE ON.  Let us know, thanks.