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.
CONVERT(CHAR(100), SERVERPROPERTY('Servername')) AS Server,
WHEN 'D' THEN 'Database'
WHEN 'L' THEN 'Log'
END AS backup_type,
msdb.dbo.backupset.name AS backupset_name,
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)