Sql-server – BACKUP failed to complete the command BACKUP DATABASE

Well, it looks like 3041 is the generic "something went boom with the backup" error.

Have you tried just running the backup SQL from SQL Agent without using the wrapping stored procedure? I'm assuming the stored procedure you're using for the backup lives in the master DB (or at least not in the DB you're backing up).

Also, you could use this query to check your backup status (last 7 days). There might be something else going on that you don't know about and that's interfering with your backups.

SELECT  
 CONVERT(CHAR(100), SERVERPROPERTY('Servername')) AS Server, 
 msdb.dbo.backupset.database_name,  
 msdb.dbo.backupset.backup_start_date,  
 msdb.dbo.backupset.backup_finish_date, 
 msdb.dbo.backupset.expiration_date, 
 CASE msdb..backupset.type  
   WHEN 'D' THEN 'Database'  
   WHEN 'L' THEN 'Log'  
 END AS backup_type,  
 msdb.dbo.backupset.backup_size,  
 msdb.dbo.backupmediafamily.logical_device_name,  
 msdb.dbo.backupmediafamily.physical_device_name,   
 msdb.dbo.backupset.name AS backupset_name, 
 msdb.dbo.backupset.description 
FROM   msdb.dbo.backupmediafamily  
INNER JOIN msdb.dbo.backupset ON msdb.dbo.backupmediafamily.media_set_id = msdb.dbo.backupset.media_set_id  
WHERE  (CONVERT(datetime, msdb.dbo.backupset.backup_start_date, 102) >= GETDATE() - 7)  
ORDER BY  
  msdb.dbo.backupset.database_name, 
  msdb.dbo.backupset.backup_finish_date 

Fixed this - VSS Writer had fallen over for some reason, and the upshot of that was that a load of stuff (BACKUP amongst them) could not complete (BlkBy column in sp_who2 showed this up). A reboot of the server fixed this issue (services.msc wouldn't let me kill VSS Writer, and neither would the KILL command)...only thing left to do is find out WHY it happened.

And sort myself a disaster recovery plan ;)