BACKUP failed to complete - with spaces, for no reason
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) &gt;= GETDATE() - 7)  
ORDER BY  
  msdb.dbo.backupset.database_name, 
  msdb.dbo.backupset.backup_finish_date