I enabled a maintenance plan on a SQL server which creates a full backup of all databases.  When checking the job history I noticed that the job had failed.  Upon further investigation I could see that although the job had failed, all the databases had been backed up.  Opening the job log revealled the following error:

Failed:(-1073548784) Executing the query “BACKUP DATABASE [master] TO  DISK = N’I:\\Microsoft SQL Server\\MSSQL.1\\MSSQL\\Backup\\master\\master_backup_201010260000.bak’ WITH NOFORMAT, NOINIT,  NAME = N’master_backup_20101026000019′, SKIP, REWIND, NOUNLOAD,  STATS = 10
” failed with the following error: “Transaction (Process ID 580) was deadlocked on lock resources with another process and has been chosen as the deadlock victim. Rerun the transaction.
Could not insert a backup or restore history/detail record in the msdb database. This may indicate a problem with the msdb database. The backup/restore operation was still successful.

I checked the SQL job schedule and noticed that another “Cleanup History” maintenance plan was set to run at the same time.  In order for this maintenance plan to cleanup the job history is needs to access MSDB, which caused the deadlock.  Re-scheduling the Full Backup plan to run 5 minutes later cured the problem